Is such transformation for a given array possible?

Question

My friend asked me this question and I am not able to solve it even I am not getting how to think about such problem. Please provide a good method?

Given $n$ numbers, you can perform the following operation any number of times : Choose any subset of the numbers (possibly empty), none of which are $0$. Decrement the numbers in the subset by $1$, and increment the numbers not in the subset by $K$. Is it possible to perform operations such that exactly $n - 1$ numbers become $0$?

Constraints :

2 <= n <= 100

1 <= K <= 10

0 <= array element<= 1000

Answer 1

Assuming that $K$ is some positive integer constant, then there exists a method iff all but one share the same remainder mod $(K+1)$.

To see why solutions exist only when $n-1$ of them share the same remainder, consider any arbitrary set of $s$ operations, and two of the numbers, $x_a$ and $x_b$.

If $x_a$ is decremented $a$ times and incremented $s-a$ times, while $x_b$ is decremented $b$ times and incremented $s-b$ times, the net change of $x_a$ is that it increased by $Ks - (K+1)a$, while $x_b$ increased by $Ks - (K+1)b$. Thus, the difference between them changed by $(K+1)(a - b)$. In other words, $x_a - x_b$ could only have changed by a multiple of $(K+1)$. If the difference between them wasn't a multiple of $(K+1)$ before, it can't be 0 now, and thus $x_a$ and $x_b$ wouldn't even be equal, much less both 0.

Now that we've established that solutions only exist when $n-1$ of them share the same remainder, I will show how to actually do it when this case arises.

Let $x_i$ be one of the numbers. The basic idea is to consider the next $(K+1)$ moves as one iteration. The aggregate result of this iteration is:

• $x_i$ gets incremented twice and decremented $K-1$ times, for a total net increase of $2K - (K-1) = K+1$
• All other numbers will be incremented once and decremented $K$ times, for a total net increase of $K - K = 0$.

It's not too hard to see that we can create and use such an iteration.

So, suppose $x_t$ is the "odd one out". All we do then is do the above $(K+1)$-step iteration on each of the others until they are all equal (which can be done since they all have the same remainder mod $K+1$). Once all $n-1$ are equal, just decrement them all to 0.

---

EDIT: Addenda

Technically, the above iteration might run into problems if one of the variables is less than $K$ (the iteration might make it go negative in the middle). To fix this, what you can do is first prime everything with small singleton decrements until all variables are at least $K$. Then, you can do the iterations as needed.