RAP - Editorial

Problem Link :–

Contest

Practice

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.

1 Like
//