Editorial for SUMNCR - PELT2019

Problem setter: aditya10_

Problem Code: SUMNCR

Difficulty: Easy-Medium

Prerequisites: Observation, Implementation

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

1 Like

Instead one can observe that for any number , nCi would be even if i is equal to power of 2 raise to first unset bit in binary representation of the corresponding number.

For instance(n = 13) , binary representation is 1101 , i would be equal to 2.

But for n = 7 , suitable i does not exist.

1 Like

We can also use lucas theorem to prove it.


Why is r in nCr always a power of 2 for getting nCr as an even value?

because only at these value there is a chance of the power of 2 in numerator can overtake power of 2 in denominator