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
1 Like