A shopkeeper has a sale to complete and has arranged the items being sold in a list.
Starting from the left, the shop keeper rings up each item at its full price less the price of the first lower or equally priced item to its right.
If there is no item to the right that costs less than or equal to the current item's price the current item is sold at full price.
Assumptions
The first and second items would each be discounted by 1 unit, the first equal or lower price to the right.
The item priced 1 unit would sell at a full price.
The next item, at 2 units, would be discounted 2 units as would the 4 unit item.
The sixth and final item must be purchased at full price.
Input
The input consists of one arguments:
items_prices : a list of integers representing the price of items
Output
return total cost of all items on the first line and on the second line print a space separated list of integers representing the indexes of the non- discounted items in ascending index order.
Constraints
1 <= size(prices) <= 100000
1 <= prices <= 1000000
Examples
Example 1:
Input:
items_prices = [2, 3, 1, 2, 4, 2]
Output:
18
2 5
Explanation:
The total cost is 1+2+1+0+2+2 = 8 units. And 2 and 5 indexes has no discount.
Examples
Example 2:
Input:
items_prices = [5, 1, 3, 4, 6, 2]
Output:
14
1 5
Examples
Example 3:
Input:
items_prices = [1, 3, 3, 2, 5]
Output:
9
0 3 4
Starting from the left, the shop keeper rings up each item at its full price less the price of the first lower or equally priced item to its right.
If there is no item to the right that costs less than or equal to the current item's price the current item is sold at full price.
Assumptions
The first and second items would each be discounted by 1 unit, the first equal or lower price to the right.
The item priced 1 unit would sell at a full price.
The next item, at 2 units, would be discounted 2 units as would the 4 unit item.
The sixth and final item must be purchased at full price.
Input
The input consists of one arguments:
items_prices : a list of integers representing the price of items
Output
return total cost of all items on the first line and on the second line print a space separated list of integers representing the indexes of the non- discounted items in ascending index order.
Constraints
1 <= size(prices) <= 100000
1 <= prices <= 1000000
Examples
Example 1:
Input:
items_prices = [2, 3, 1, 2, 4, 2]
Output:
18
2 5
Explanation:
The total cost is 1+2+1+0+2+2 = 8 units. And 2 and 5 indexes has no discount.
Examples
Example 2:
Input:
items_prices = [5, 1, 3, 4, 6, 2]
Output:
14
1 5
Examples
Example 3:
Input:
items_prices = [1, 3, 3, 2, 5]
Output:
9
0 3 4
Get one-to-one training from Google Facebook engineers
Top-notch Professionals
Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.
Customized Private Class
Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.