Odd numbers in N-th row of Pascal’s Triangle
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:
4
Time Complexity: O(L), where L is the length of a binary representation of a given N.
Space Complexity: O(1)