Minimize operations to reduce price difference
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are managing an inventory of products and want to adjust their prices.
There are `n` products. The price of the *i*-th product is given by an integer array `prices` of length `n`.
You are also given two integers:
- `k` — the maximum absolute amount by which a product's price can be adjusted (increased or decreased) in a **single** operation.
- `d` — the **target price difference** threshold.
Your goal is to perform a sequence of allowed operations so that the difference between the **highest** and **lowest** prices in the inventory becomes **strictly less than** `d`, i.e.:
> `max(prices) - min(prices) < d`
### Allowed operation
You may perform the following operation any number of times (possibly zero):
1. Choose two indices `x` and `y` such that `1 <= x <= y <= n`.
2. Choose an integer `p` such that `1 <= p <= k`.
3. Update the prices as:
- `prices[x] = prices[x] + p`
- `prices[y] = prices[y] - p`
Notes:
- It is allowed that `x == y`, but then the net change is `+p` and `-p` on the same element, which cancels out and has no effect (so such an operation is useless in practice).
- You may assume all intermediate prices can be any integers (no additional constraints such as non-negativity unless explicitly stated in the actual implementation setting).
### Task
Given:
- an integer `n`,
- an integer array `prices` of length `n`,
- integers `k` and `d`,
find the **minimum number of operations** required so that after performing these operations, the following holds:
> `max(prices) - min(prices) < d`.
If it is impossible (under the given constraints and allowed operation), specify what value your function should return (e.g., `-1`), or assume inputs are such that it is always possible.
### Input assumptions
You may assume, for purposes of algorithm design:
- `1 <= n <= 10^5`.
- `1 <= k, d <= 10^9`.
- `-10^9 <= prices[i] <= 10^9`.
### Output
- Return a single integer: the **minimum number of operations** needed to achieve `max(prices) - min(prices) < d`.
### Complexity requirement
Design an algorithm efficient enough for `n` up to about `10^5`.
Quick Answer: This question evaluates algorithm design and array-manipulation skills, focusing on reasoning about constrained transfers of value, invariants, and the minimization of operation counts under a fixed per-operation bound.
Return the minimum number of operations needed to make max(prices)-min(prices)<d, where each operation transfers up to k units from one product to another.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,10], 3, 3)
Expected Output: 2
Explanation: Transfer from high to low until range less than 3.
Input: ([5,6,7], 2, 5)
Expected Output: 0
Explanation: Already within range.
Input: ([0,100,100], 10, 10)
Expected Output: 7
Explanation: Must move mass toward a feasible narrow interval.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.