# Count odd and even Binomial Coefficients of N-th power

Given an integer N, the task is to count the number of even and odd binomial coefficients up to Nth power.

Examples:

Input: N = 4
Output:
Odd: 2
Even: 3
Explanation:
The binomial coefficients are as follows:
4C0 = 1, 4C1 = 4 , 4C2 = 6 , 4C3 = 4 , 4C4 = 1.
Therefore, it can be observed that there exists exactly 2 odd and 3 even Binomial Coefficients.

Input: N = 5
Output:
Odd: 4
Even: 2
Explanation:
The binomial coefficients are as follows:
5C0 = 1, 5C1 = 5, 5C2 = 10, 5C3 = 10, 5C4 = 5, 5C5 = 1.
Therefore, there are 4 odd and 2 even coefficients.

Solution Approach: The idea to solve this problem is using Bit Manipulation. Find the set bits in the given integer N. Count of odd binomial coefficients are equal to 2 ^ Count of Set Bits in N. Similarly the count of even binomial coefficients is equal to (N + 1 – 2 ^ Count of Set Bits in N).

Below is the implementation of the above approach:

## C++

 `// C++ program for the above approach`   `#include ` `#include ` `using` `namespace` `std;`   `// Function to count set bits in` `// binary representation of number N` `int` `countSetBits(``int` `N)` `{` `    ``int` `count = 0;`   `    ``// Count set bits in N` `    ``while` `(N) {`   `        ``N = N & (N - 1);` `        ``count++;` `    ``}`   `    ``// Return the final count` `    ``return` `count;` `}`   `// Driver Code` `int` `main()` `{` `    ``int` `N = 4;`   `    ``int` `bits = countSetBits(N);`   `    ``// Print odd Binomial coefficients` `    ``cout << ``"Odd "` `         ``<< ``": "` `<< ``pow``(2, bits) << ``"\n"``;`   `    ``// Print even Binomial coefficients` `    ``cout << ``"Even "` `         ``<< ``": "` `<< N + 1 - ``pow``(2, bits)` `         ``<< ``"\n"``;`   `    ``return` `0;` `}`

## Java

 `// Java program for the above approach ` `import` `java.util.*;` ` `  `class` `GFG{` `     `  `// Function to count set bits in` `// binary representation of number N` `static` `int` `countSetBits(``int` `N)` `{` `    ``int` `count = ``0``;` ` `  `    ``// Count set bits in N` `    ``while` `(N != ``0``)` `    ``{` `        `  `        ``N = N & (N - ``1``);` `        ``count++;` `    ``}` ` `  `    ``// Return the final count` `    ``return` `count;` `}` ` `  `// Driver code` `public` `static` `void` `main(String[] args)` `{` `    ``int` `N = ``4``;` ` `  `    ``int` `bits = countSetBits(N);` ` `  `    ``// Print odd Binomial coefficients` `    ``System.out.println(``"Odd "` `+ ``": "` `+` `               ``(``int``)(Math.pow(``2``, bits)));` ` `  `    ``// Print even Binomial coefficients` `    ``System.out.println(``"Even "` `+ ``": "` `+` `               ``(N + ``1` `- (``int``)(Math.pow(``2``, bits))));` `}` `}`   `// This code is contributed by susmitakundugoaldanga`

## Python3

 `# Python3 program for the above approach`   `# Function to count set bits in` `# binary representation of number N` `def` `countSetBits(N: ``int``) ``-``> ``int``:`   `    ``count ``=` `0`   `    ``# Count set bits in N` `    ``while` `(N):` `        ``N ``=` `N & (N ``-` `1``)` `        ``count ``+``=` `1`   `    ``# Return the final count` `    ``return` `count`   `# Driver Code` `if` `__name__ ``=``=` `"__main__"``:`   `    ``N ``=` `4`   `    ``bits ``=` `countSetBits(N)`   `    ``# Print odd Binomial coefficients` `    ``print``(``"Odd : {}"``.``format``(``pow``(``2``, bits)))`   `    ``# Print even Binomial coefficients` `    ``print``(``"Even : {}"``.``format``(N ``+` `1` `-` `pow``(``2``, bits)))`   `# This code is contributed by sanjeev2552`

## C#

 `// C# program for the above approach ` `using` `System;` ` `  `class` `GFG{` ` `  `// Function to count set bits in` `// binary representation of number N` `static` `int` `countSetBits(``int` `N)` `{` `    ``int` `count = 0;` `  `  `    ``// Count set bits in N` `    ``while` `(N != 0)` `    ``{` `        ``N = N & (N - 1);` `        ``count++;` `    ``}` `  `  `    ``// Return the final count` `    ``return` `count;` `}` ` `  `// Driver Code` `public` `static` `void` `Main()` `{` `    ``int` `N = 4;` `    ``int` `bits = countSetBits(N);` `  `  `    ``// Print odd Binomial coefficients` `    ``Console.WriteLine(``"Odd "` `+ ``": "` `+` `                     ``(``int``)(Math.Pow(2, bits)));` `  `  `    ``// Print even Binomial coefficients` `    ``Console.WriteLine(``"Even "` `+ ``": "` `+` `                     ``(N + 1 - (``int``)(Math.Pow(2, bits))));` `}` `}`   `// This code is contributed by sanjoy_62`

## Javascript

 ``

Output

```Odd : 2
Even : 3

```

Time Complexity: O(log N), where N is the input number
Auxiliary Space: O(1)

Approach: To count the number of odd and even binomial coefficients of N-th power, we can use the following approach

1. Initialize two counters, one for counting odd coefficients and one for counting even coefficients, to zero.
2. Loop through all possible values of k from 0 to N.
3. For each value of k, calculate the binomial coefficient C(N, k) using the formula: C(N, k) = N! / (k! * (N – k)!) where “!” denotes the factorial function.
4. Check if the calculated binomial coefficient is odd or even. If it’s odd, increment the counter for odd coefficients. If it’s even, increment the counter for even coefficients. After the loop, the counters will contain the total count of odd and even binomial coefficients for N-th power.

## C++

 `#include ` `#include // Include the tuple library`   `using` `namespace` `std;`   `tuple<``int``, ``int``> count_odd_even_binomial_coefficients(``int` `N) {` `    ``int` `odd_count = 0;` `    ``int` `even_count = 0;`   `    ``for` `(``int` `k = 0; k <= N; k++) {` `        ``int` `coefficient = 1;` `        ``for` `(``int` `i = 1; i <= k; i++) {` `            ``coefficient = coefficient * (N - i + 1) / i;` `        ``}`   `        ``if` `(coefficient % 2 == 0) {` `            ``even_count++;` `        ``} ``else` `{` `            ``odd_count++;` `        ``}` `    ``}`   `    ``return` `make_tuple(odd_count, even_count); ``// Use make_tuple to return a tuple` `}`   `int` `main() {` `    ``int` `N = 4;` `    ``int` `odd_count, even_count;` `    ``tie(odd_count, even_count) = count_odd_even_binomial_coefficients(N);` `    ``cout << ``"Odd: "` `<< odd_count << endl;` `    ``cout << ``"Even: "` `<< even_count << endl;`   `    ``return` `0;` `}`

## Java

 `import` `java.util.*;`   `public` `class` `Main {` `    `  `    ``// Define a function to count odd and even binomial coefficients` `    ``public` `static` `int``[] countOddEvenBinomialCoefficients(``int` `N) {` `        ``int` `oddCount = ``0``;` `        ``int` `evenCount = ``0``;`   `        ``for` `(``int` `k = ``0``; k <= N; k++) {` `            ``int` `coefficient = ``1``;` `            ``for` `(``int` `i = ``1``; i <= k; i++) {` `                ``coefficient = coefficient * (N - i + ``1``) / i;` `            ``}`   `            ``if` `(coefficient % ``2` `== ``0``) {` `                ``evenCount++;` `            ``} ``else` `{` `                ``oddCount++;` `            ``}` `        ``}`   `        ``return` `new` `int``[]{oddCount, evenCount}; ``// Return an array instead of a tuple` `    ``}`   `    ``public` `static` `void` `main(String[] args) {` `        ``int` `N = ``4``;` `        ``int``[] counts = countOddEvenBinomialCoefficients(N);` `        ``int` `oddCount = counts[``0``];` `        ``int` `evenCount = counts[``1``];`   `        ``System.out.println(``"Odd: "` `+ oddCount);` `        ``System.out.println(``"Even: "` `+ evenCount);` `    ``}` `}`

## Python3

 `# Function to count odd and even binomial coefficients` `def` `count_odd_even_binomial_coefficients(N):` `    ``odd_count ``=` `0`  `# Variable to store the count of odd coefficients` `    ``even_count ``=` `0`  `# Variable to store the count of even coefficients`   `    ``# Loop through all possible coefficients` `    ``for` `k ``in` `range``(N ``+` `1``):` `        ``coefficient ``=` `1`   `        ``# Calculate the binomial coefficient for the current k` `        ``for` `i ``in` `range``(``1``, k ``+` `1``):` `            ``coefficient ``=` `(coefficient ``*` `(N ``-` `i ``+` `1``)) ``/``/` `i`   `        ``# Check if the coefficient is even or odd` `        ``if` `coefficient ``%` `2` `=``=` `0``:` `            ``even_count ``+``=` `1` `        ``else``:` `            ``odd_count ``+``=` `1`   `    ``# Return the counts of odd and even coefficients as a tuple` `    ``return` `odd_count, even_count`   `# Set the value of N` `N ``=` `4`   `# Call the counting function` `odd_count, even_count ``=` `count_odd_even_binomial_coefficients(N)`   `# Print the count of odd and even coefficients` `print``(``"Odd:"``, odd_count)` `print``(``"Even:"``, even_count)`

## C#

 `using` `System;`   `class` `Program` `{` `    ``// Function to count odd and even binomial coefficients for a given N` `    ``static` `(``int` `oddCount, ``int` `evenCount) CountOddEvenBinomialCoefficients(``int` `N)` `    ``{` `        ``int` `oddCount = 0;` `        ``int` `evenCount = 0;`   `        ``// Iterate through all binomial coefficients from k=0 to k=N` `        ``for` `(``int` `k = 0; k <= N; k++)` `        ``{` `            ``int` `coefficient = 1;` `            `  `            ``// Calculate the binomial coefficient using a loop` `            ``for` `(``int` `i = 1; i <= k; i++)` `            ``{` `                ``coefficient = coefficient * (N - i + 1) / i;` `            ``}`   `            ``// Check if the coefficient is even or odd and update counts` `            ``if` `(coefficient % 2 == 0)` `            ``{` `                ``evenCount++;` `            ``}` `            ``else` `            ``{` `                ``oddCount++;` `            ``}` `        ``}`   `        ``// Return a tuple containing the counts of odd and even coefficients` `        ``return` `(oddCount, evenCount);` `    ``}`   `    ``static` `void` `Main()` `    ``{` `        ``int` `N = 4;` `        `  `        ``// Call the CountOddEvenBinomialCoefficients function to get counts` `        ``(``int` `oddCount, ``int` `evenCount) = CountOddEvenBinomialCoefficients(N);`   `        ``// Print the counts of odd and even coefficients` `        ``Console.WriteLine(``"Odd: "` `+ oddCount);` `        ``Console.WriteLine(``"Even: "` `+ evenCount);` `    ``}` `}`

## Javascript

 `// Function to count odd and even binomial coefficients` `function` `count_odd_even_binomial_coefficients(N) {` `    ``let odd_count = 0; ``// Variable to store the count of odd coefficients` `    ``let even_count = 0; ``// Variable to store the count of even coefficients`   `    ``// Loop through all possible coefficients` `    ``for` `(let k = 0; k <= N; k++) {` `        ``let coefficient = 1;`   `        ``// Calculate the binomial coefficient for the current k` `        ``for` `(let i = 1; i <= k; i++) {` `            ``coefficient = (coefficient * (N - i + 1)) / i;` `        ``}`   `        ``// Check if the coefficient is even or odd` `        ``if` `(coefficient % 2 === 0) {` `            ``even_count++;` `        ``} ``else` `{` `            ``odd_count++;` `        ``}` `    ``}`   `    ``// Return the counts of odd and even coefficients as an array` `    ``return` `[odd_count, even_count];` `}`   `// Main function` `function` `main() {` `    ``const N = 4; ``// Set the value of N` `    ``const [odd_count, even_count] = count_odd_even_binomial_coefficients(N); ``// Call the counting function` `    ``console.log(``"Odd:"``, odd_count); ``// Print the count of odd coefficients` `    ``console.log(``"Even:"``, even_count); ``// Print the count of even coefficients` `}`   `// Call the main function to start the program` `main();`

Output

```Odd: 2
Even: 3

```

Time Complexity: O(N^2), where N is the input parameter.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Previous
Next
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}