If \(D=0\)

If \(D=0\), then \(|A_i-A_j|=0 \Leftrightarrow A_i=A_j\), so it is sufficient to exclude repeated values in \(A\).

If \(A\) has \(X\) distinct values, each of them can be retained only once, so \(B\) can have a length of at most \(X\). Thus, at least \((N-X)\) operations are required.

If \(D \geq 1\)

Suppose that \(x \; (0 \leq x \leq 10^6)\) occurs \(C_x\) times in \(A\). Removing an element of \(A\) corresponds to decreasing a non-zero element of \(C\) by one. Also, the existence of \((i,j)\) with \(|A_i-A_j|=D\) corresponds to the existence of \(x\) with \(C_x>0\) and \(C_{x+D}>0\). Thus, the problem can be rephrased as follows:

• You may choose a non-zero element of \(C_x\) and decrement by one in one operation. How many such operations is required to make \(C_x=0\) or \(C_{x+D}=0\) for all \(x\)?

The condition “\(C_x=0\) or \(C_{x+D}=0\) for all \(x\)” can be decomposed as follows, utilizing \(x\operatorname{mod} D\):

• for all \(i=0,1,\dots,D-1\) it holds that:
  • for all \(j=0,1,\dots,\lfloor (10^6-i) / D \rfloor - 1\), it holds that \(C_{i+Dj}=0\) or \(C_{i+D(j+1)}=0\).

Solution with Dynamic Programming (DP)

This problem can be solved for each \(i=0,1,\dots,D-1\) independently. We use Dynamic Programming (DP). Fix \(i\), and let \(\mathrm{dp}[j]\) be “the minimum number of operations required to make \(C_{i},C_{i+D},\dots,C_{i+Dj}\) satisfy the condition.

Supposing that we know \(\mathrm{dp}[0],\dots,\mathrm{dp}[j]\), we consider how to find \(\mathrm{dp}[j+1]\). We consider two cases, whether to make \(C_{i+D(j+1)} = 0\) or not.

• If we make \(C_{i+D(j+1)} = 0\): we need to perform \(C_{i+D(j+1)}\) operations. In this case, \(C_{i+Dj}\) can be any value, and the overall number of operations is \(\mathrm{dp}[j]+C_{i+D(j+1)}\).
• If we do not make \(C_{i+D(j+1)}\): no operations are needed against \(C_{i+D(j+1)}\). In this case, \(C_{i+Dj}\) must be made \(0\), and \(C_{i},\dots,C_{i+D(j-1)}\) must satisfy the conditions. The overall number of operations is \(\mathrm{dp}[j-1] + C_{i+Dj}\).

We make the smaller of the two above, so we obtain the recurrence relations \(\mathrm{dp}[j+1] = \min\{\mathrm{dp}[j]+C_{i+D(j-1)},\mathrm{dp}[j-1]+C_{i+Dj}\}\). The answer is \(\mathrm{dp}[\lfloor (10^6-i) / D \rfloor]\).

Evaluating the DP for each \(i\), the answer is found as the sum of the results. The time complexity is \(O(M)\), where \(M=10^6\).

Sample code (Python)