×

# Editorial for SUMNCR - PELT2019

 1 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 asked 11 Jan, 18:44 5★panik 116●6 accept rate: 7%

 4 We can also use lucas theorem to prove it. answered 12 Jan, 01:26 5★abhayps 42●1 accept rate: 0%
 1 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 5★nikesh48 36●3 accept rate: 20%
 0 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 3●2 accept rate: 0% 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) panik5★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,648
×814
×212
×10
×4
×2