Shopkeeper Final Price
Updated
Problem statement
A shopkeeper arranges items in a list for a sale. Starting from the left, each item is sold at its full price minus the price of the first item to its right that is of equal or lower price.
If no such item exists, the current item is sold at its full price.
Print the sum of the final cost for all items, then on the next line print a space-separated, 0-based list of the indices of items that are sold at full price, in ascending order.
Complete the function finalPrice in the editor with the following parameter:
int prices[n]: an array of item prices
Return a two-element String[] representing the required output lines: the total cost as the first string, and the space-separated full-price item indices as the second string.
1 <= n <= 10^51 <= prices[j] <= 10^9, where0 <= j < n
Function
finalPrice(prices: int[]) → String[]Examples
Example 1
prices = [9, 2, 1, 2, 4, 2]return = ["13","2 5"]For item prices [9, 2, 1, 2, 4, 2]:
- Item
0, priced at9, is discounted by the next item priced2, so its final cost is7. - Item
1, priced at2, is discounted by the next equal-or-lower item priced1, so its final cost is1. - Item
2, priced at1, sells at full price because there is no equal-or-lower item to its right. - Item
3, priced at2, is discounted by the later item priced2, so its final cost is0. - Item
4, priced at4, is discounted by the later item priced2, so its final cost is2. - Item
5, priced at2, sells at full price.
The total cost is 7 + 1 + 1 + 0 + 2 + 2 = 13, and the full-price item indices are 2 5.
The output lines are 13 and 2 5.
Example 2
prices = [5, 1, 3, 4, 6, 2]return = ["14","1 5"]For item prices [5, 1, 3, 4, 6, 2]:
- Item
0, priced at5, is discounted by the next item priced1, so its final cost is4. - Item
1, priced at1, sells at full price because there is no equal-or-lower item to its right. - Item
2, priced at3, is discounted by the later item priced2, so its final cost is1. - Item
3, priced at4, is discounted by the later item priced2, so its final cost is2. - Item
4, priced at6, is discounted by the later item priced2, so its final cost is4. - Item
5, priced at2, sells at full price.
The total cost is 4 + 1 + 1 + 2 + 4 + 2 = 14, and the full-price item indices are 1 5.
The output lines are 14 and 1 5.
More Uber Online Assessment questions
- Count Palindromic Ancestor PathsOA · Seen Aug 2026
- Jump Game with Prime-3 StepsOA · Seen Aug 2026
- Last Truck to Leave the LaneOA · Seen Jul 2026
- Chain of CommandOA · Seen Jul 2026
- Total Palindrome Substring CostOA · Seen Jun 2026
- Jump Game with Prime-Step RuleOA · Seen May 2026
- Pipeline Throughput Maximization Under BudgetOA · Seen May 2026
- Balanced Prefix Sets in a PermutationOA · Seen Apr 2026
- Minimum Edge Reversals to Root a TreeOA · Seen Apr 2026
- Maximum Riders in CarOA · Seen Apr 2026
Similar questions at other companies
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Sum of Subarray MinimumsNVIDIA · OANVIDIA interview questions
- Shopkeeper Final Price SummaryMicrosoft · OAMicrosoft interview questions
- Nested Recipe Blocks (Game Adaptation)Roblox · OARoblox interview questions
- Maximum Capped Histogram Area After One RemovalMyntra · OAMyntra interview questions
- Steps to the Next Higher Value in a CircleRippling · OARippling interview questions
- Predict AnswerAmazon · OA
- Retention Policy CollisionBox · OABox interview questions
- Longest Prefix-Valid Binary SubarrayHackerRank · OAHackerRank interview questions
- Sum of Subarray RegionsPatreon · OA