Compute discounted prices and full-price indices

Q: Compute discounted prices and full-price indices

This question evaluates array-processing skills, competency with next-smaller-or-equal element patterns, and the ability to compute aggregated results under ordering constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an array prices of length $n$ . Items are sold from left to right, and each item’s final selling price is computed as follows:

For item $i$ :

Find the first index $j > i$ such that prices[j] <= prices[i] .
If such $j$ exists, the final price is prices[i] - prices[j] .
Otherwise, the final price is prices[i] (sold at full price).

You must output two lines:

The total of all final prices.
All indices (0-based) of items that are sold at full price , in increasing order.

Input

Integer $n$
Array prices of length $n$

Output

Line 1: integer total final price
Line 2: space-separated 0-based indices sold at full price (print an empty line if none)

Example (informal)

If prices = [5, 1, 3], then item 0 is discounted by 1 (final 4), item 1 has no qualifying item to its right (final 1), item 2 has none (final 3). Total = 8, full-price indices = 1 2.

Compute discounted prices and full-price indices

Quick Overview

Input

Output

Example (informal)

Comments (0)