Odd numbers in N-th row of Pascal’s Triangle

0 0 4 minutes read

Given N, the row number of Pascal’s triangle(row starting from 0). Find the count of odd numbers in the N-th row of Pascal’s Triangle.
Prerequisite: Pascal’s Triangle | Count number of 1’s in binary representation of N

Examples:

Input : 11
Output : 8

Input : 20
Output : 4

Approach: It appears the answer is always a power of 2. In fact, the following theorem exists:
THEOREM: The number of odd entries in row N of Pascal’s Triangle is 2 raised to the number of 1’s in the binary expansion of N.
Example: Since 83 = 64 + 16 + 2 + 1 has binary expansion (1010011), then row 83 has pow(2, 4) = 16 odd numbers.

Below is the implementation of the above approach:

C++

   
// CPP code to find the count of odd numbers
// in n-th row of Pascal's Triangle
#include <bits/stdc++.h>     
using namespace std ;
 
/* Function to get no of set
   bits in binary representation 
   of positive integer n */
int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
        count += n & 1;
        n >>= 1;
    }
     
    return count;
}
 
int countOfOddsPascal(int n)
{
    // Count number of 1's in binary
    // representation of n.
    int c = countSetBits(n);
     
    // Number of odd numbers in n-th
    // row is 2 raised to power the count.
    return pow(2, c);
}
 
// Driver code
int main()
{
    int n = 20;    
    cout << countOfOddsPascal(n) ;    
    return 0;
}

Java

// Java code to find the count of odd
// numbers in n-th row of Pascal's 
// Triangle
import java.io.*;
 
class GFG {
     
    /* Function to get no of set
    bits in binary representation 
    of positive integer n */
    static int countSetBits(int n)
    {
        long count = 0;
        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }
         
        return (int)count;
    }
     
    static int countOfOddsPascal(int n)
    {
         
        // Count number of 1's in binary
        // representation of n.
        int c = countSetBits(n);
         
        // Number of odd numbers in n-th
        // row is 2 raised to power the
        // count.
        return (int)Math.pow(2, c);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 20; 
        System.out.println(
                     countOfOddsPascal(n));
    }
}
 
// This code is contributed by anuj_67.

Python3

# Python code to find the count of
# odd numbers in n-th row of 
# Pascal's Triangle
 
# Function to get no of set
# bits in binary representation
# of positive integer n
def countSetBits(n):
    count =0
    while n:
        count += n & 1
        n >>= 1
         
    return count
 
def countOfOddPascal(n):
 
    # Count number of 1's in binary
    # representation of n.
    c = countSetBits(n)
 
    # Number of odd numbers in n-th
    # row is 2 raised to power the count.
    return pow(2, c)
 
# Driver Program
n = 20
print(countOfOddPascal(n))
 
# This code is contributed by Shrikant13

C#

// C# code to find the count of odd numbers
// in n-th row of Pascal's Triangle
using System;
 
class GFG {
     
    /* Function to get no of set
    bits in binary representation 
    of positive integer n */
    static int countSetBits(int n)
    {
        int count = 0;
        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }
         
        return count;
    }
     
    static int countOfOddsPascal(int n)
    {
        // Count number of 1's in binary
        // representation of n.
        int c = countSetBits(n);
         
        // Number of odd numbers in n-th
        // row is 2 raised to power the
        // count.
        return (int)Math.Pow(2, c);
    }
     
    // Driver code
    public static void Main () 
    {
        int n = 20; 
        Console.WriteLine(
                 countOfOddsPascal(n)) ; 
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// PHP code to find the 
// count of odd numbers
// in n-th row of Pascal's 
// Triangle
 
/* Function to get no of set
   bits in binary representation 
   of positive integer n */
function countSetBits($n)
{
    $count = 0;
    while ($n)
    {
        $count += $n & 1;
        $n >>= 1;
    }
     
    return $count;
}
 
function countOfOddsPascal($n)
{
     
    // Count number of 1's in binary
    // representation of n.
    $c = countSetBits($n);
     
    // Number of odd numbers in n-th
    // row is 2 raised to power the count.
    return pow(2, $c);
}
 
    // Driver code
    $n = 20; 
    echo countOfOddsPascal($n) ; 
 
// This code is contributed by mits. 
?>

Javascript

<script>    
    // Javascript code to find the count of odd numbers
    // in n-th row of Pascal's Triangle
     
    /* Function to get no of set
    bits in binary representation 
    of positive integer n */
    function countSetBits(n)
    {
        let count = 0;
        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }
           
        return count;
    }
       
    function countOfOddsPascal(n)
    {
        // Count number of 1's in binary
        // representation of n.
        let c = countSetBits(n);
           
        // Number of odd numbers in n-th
        // row is 2 raised to power the
        // count.
        return Math.pow(2, c);
    }
     
    let n = 20; 
    document.write(countOfOddsPascal(n)) ;
     
</script>

Output:

Time Complexity: O(L), where L is the length of a binary representation of a given N.

Space Complexity: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!