 # Editorial for Dream of Divisibility DREDIV?

I am not able to find editorial of Dream of Divisibility DREDIV Problem of Jan 21 Lunchtime on Codechef Discuss?
I am searching for the text editorial of DREDIV as I am not able to understand the video editorial of DREDIV?
Thanks.

None of the written editorials of JAN Lunchtime are out.
Wait for some time.

3 Likes

Okay . I will wait then . If someone can explain then he/she may reply on this thread .

I am facing one doubt that How the solution is related to power of 2 . I dont understand this.

suppose you take the test case 6 6 8 7 3 and its given a[i]=a[i]+a[j] if i=1 and j=1 it means that the every time we add it to itself its sum will increase multiple of power of two like 6+6=12 which is 6 X 2 and 12+12=24 that is 6 X 4 like this .So if k is divisble by power of two then you can easily say that the number will be divisble. if its is not so then you cant make a number divisble by k if it is not already divisible by k.
Example suppose you take
N = 2
k=3
a[]= {7 , 2}
then if you see that neither 7 is divisble by three nor 2 is divisble by three so if you take sum 7 and 2 then it will be 9 and one of them will become divisble.you can see this by taking mod of two number 7%3=1 and 2%3=2 so now a[]={1,2} and sum of 1 and 2 is three now it beomes {1,3} so now again mod by 3 array becomes {1,0} so now we cant make on divisble.

3 Likes

Any element can be multiplied by a power of 2 by adding it to itself specific number of times.
So it is safe to remove powers of 2 from K and the answer won’t change.

4 Likes

i think it makes sense

Thank you so much for the best explaination in easy words. Your logic is more easy to understand than the video editorial of codechef. Thanks fyter_112