Can anyone help me solve this question

Array Transform

The only way to ‘transform’ the given array a1,a2,a3,…,an into 0,0,0,…,0,x(x does not matter) is to have at least n-1 ai’s to be the same.If we already have at least n-1 ai’s to be the same(say ai=y), we can select the

subset containing those n-1 numbers each of which equals y,then apply decrement operation to this subset y times(the remaining nth number which was not selected will increase by k*y times but that’s none of our business)

and we are done!!

So the task is convert any n-1 numbers to a single value if they are not already same.

Procedure to achieve this:

We will select the numbers one by one and try to make that number equal to the previous numbers which are all a single value.

ie at any instant, we will have the array as y,y,y,y,…y,ai,ai+1,…an.

At this instant, we have already converted i-1 numbers to a single value y.We now consider ith number ai.

Then, we try to convert ai and all the previous y’s to a single value say m.

Ie after transformation,our array will be m,m,m,m,…,m,m,ai+1,…an.

how do we do this ‘transformation’?

We select all y’s as the ‘non-subset’ and the remaining as ‘subset’

non-subset={y,y,y,…y(i-1 numbers)}

subset={ai,ai+1,…an}

Suppose that all y’s and ai can be converted to m.

To achieve this,we apply the described operation z times.

Then we must have:

y+zk=ai-z

ai-y=(k+1)z

z=(ai-y)/(k+1)

For z to be an integer,ai-y must be a multiple of k+1.For this,ai and y both,when divided by k+1,must leave the same remainder(say r).

ie ai=(k+1)*q1+r and y=(k+1)*q2+r

If this is true (that is ai mod k+1 == y mod k+1) then z is an integer and we can convert all of y’s and ai to a single value m.

There is one important point to note here. For all the subsequent iterations,the modulus value will be the same (ie r as taken above).

This is because:

1)Initially we have had y mod k+1 = r(right!!)

2)Now we are incrementing y in multiples of k ( to make it equal to m )

3)Hence even after incrementation, m will have same modulus value when divided with k+1(ie m mod k+1 =r)

Hence for the next iteration,ai+1 must also have remainder r so that we can have i+1 numbers having a single value after applying the operations some z1 times where z1=(ai+1 - m)/(k+1)

After this long discussion,we can comeup with an inference that to achieve the desired array of exactly n-1 zeroes,we need to have any at least n-1 numbers in the original array to have the same modulus value when divided by k+1.

If we have had two different modulo values say r1 and r2.

Its still ok if all n-1 numbers have one modulo r1 and the remaining number have modulo r2.

But if we have more than 2 different modulo values, then surely we will only be able to make less than n-1 numbers to be zero.Hence we lose in this case.

Winning criteria:Any n-1 numbers(at least n-1) having the same modulo value when divided by k+1.

I will explain this with an example

N=4,K=2

A[]={1,4,10,15}

We can see that {1,4,10} have modulo r1=1 and {15} has modulo r2=0 when divided by k+1=3

The selected subset is written in curly brackets:

1,{4,10,15} -> 3,3,9,14

3,3,{9,14} -> 5,5,8,13

5,5,{8,13} -> 7,7,7,12

{7,7,7},12 -> (seven times) 0,0,0,26