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.