Minimize operations to reduce price difference

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`.