Problem setter: aditya10_ Problem Code: SUMNCR Difficulty: EasyMedium Prerequisites: Observation, Implementation Explanation:
If k is even then m1=0,m2=0,... mk=0 so ans=0 To calculate the minimum value of m for which nCm is even  We can write nCr as (n(n1) ...(nm+1)) / (2.3.4...m) We have to find this minimum k . Let us write the maximum power of 2 which divides each number . [23]  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 n1 with 2 , n3 with 4 , n5 with 6 .... nk+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 n1 with 2 ,n3 with 4, n7 with 8, n15 with 16...... in terms of maximum power of 2. Author's Solution: click here asked 11 Jan, 18:44

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. answered 12 Jan, 00:08

Why is r in nCr always a power of 2 for getting nCr as an even value?
link
This answer is marked "community wiki".
answered 12 Jan, 20:51
because only at these value there is a chance of the power of 2 in numerator can overtake power of 2 in denominator
(13 Jan, 16:39)
