Problem setter: aditya10_
Problem Code: SUMNCR
Difficulty: Easy-Medium
Prerequisites: Observation, Implementation
Explanation:
If k is even then m1=0,m2=0,… mk=0 so ans=0
If k is odd and at least one n is even then ans=1.
else for each element we have to calculate the minimum mi for which nCmi is even. ans= min(minM1 , minM2 … minMk) where minMi= minimum value of mi for which nCmi is even
To calculate the minimum value of m for which nCm is even -
We can write nCr as (n*(n-1)* …(n-m+1)) / (2.3.4…m)
Let spn=sum of power of 2 in numerator
spd=sum of power of 2 in denominator.
We have to find minimum value of m for which spn > spd.
We have to find this minimum k . Let us write the maximum power of 2 which divides each number .
[2-3] - 1,0
[4-7] - 2,0,1,0 or (2,0)(1,0)
[9-15]- 3,0,1,0,2,0,1,0 or (3,0)(1,0)(2,0,1,0)
[16-31]- 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 or (4,0)(1,0)(2,0,1,0)(3,0,1,0,2,0,1,0)
We can see that it follows a pattern. Each range being calculated using previous ranges.
We can try to find the answer for some values of n from the above pattern by comparing n-1 with 2 , n-3 with 4 , n-5 with 6 … n-k+1 with k in terms of maximum power of 2. We have to find this minimum k. You can observe from above that this minimum value will always be a perfect power of 2.
So now we only have to compare n-1 with 2 ,n-3 with 4, n-7 with 8, n-15 with 16… in terms of maximum power of 2.
Let x= 2^y where y>=1
The minimum value of x for which (n-x+1)% 2*x = 0 is the answer.
If this minimum value is greater than n than answer is -1.
Author’s Solution: click here
Tester’s Solution: click here