Problem Link :–
Author : Ranjan Kumar
Editorialist : Ranjan Kumar
Difficulty :–
Easy-Medium.
Pre-Requisites:
Maths, Bit Manipulation.
Problem Statement :–
The problem is to find all the even coefficient of a binomial expression (1+x)^N for a given value of N, the power raised to the expression (1+x).
Quick Solution:–
As we know that for the expression (1+x)^N has N+1 terms which are:—
C(N,0) + C(N,1)x + C(n,2)x^2 +………………+ C(N,N)x^N.
So in very short explanation I say that for finding the number even coefficient we can find the odd coefficient and subtract that from the N+1 so that we can get the number of even coefficients.
Now we come to a problem of finding the number of odd coefficient. For finding the number of odd coefficient we know that will count number of 1s in the Binary value of N and the final answer will be 2 to the power number of 1s.
Detailed Approach:–
We are provided with a value N that is the power of the term (1+x).
This will lead to the N+1 terms which are
C(N,0) + C(N,1)x + C(n,2)x^2 +………………+ C(N,N)x^N.
In which the coefficients are C(N,0), C(N,1), C(n,2), ………………,C(N,N)
Suppose the number of odd coefficients is o.
Then number of even coefficients is e=N+1-o.
Now for finding the number of odd coefficients we find the binary form of N.
Let us take a counter c and initialize it by 0.
Now we perform subsequent division by 2 and increase the counter when the remainder is 1 and perform this operation until the value of N is not 0.
Then o=power(2,c);
Now e=N+1-o.
Hence the required answer is e.
Time Complexity :–
O(logN)
Solution :–
Setter’s Solution can be found here.
Feel free to post comments if anything is not clear to you.