Amazon Online Assessment (OA) - Shopkeeper Sale
A shopkeeper has a sale to complete and has arranged the items being sold in a list.
Starting from the left, the shopkeeper rings up each item at its full price minus 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 argument:
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