Números impares en la N-ésima fila del Triángulo de Pascal

Dado N, el número de fila del triángulo de Pascal (fila a partir de 0). Encuentra el conteo de números impares en la N-ésima fila del Triángulo de Pascal.
Prerrequisito: Triángulo de Pascal | Cuente el número de 1 en representación binaria de N

Ejemplos:  

Input : 11
Output : 8

Input : 20
Output : 4 

Enfoque: Parece que la respuesta es siempre una potencia de 2. De hecho, existe el siguiente teorema: 
TEOREMA: El número de entradas impares en la fila N del Triángulo de Pascal es 2 elevado al número de 1 en la expansión binaria de N. 
Ejemplo : Como 83 = 64 + 16 + 2 + 1 tiene expansión binaria (1010011), entonces la fila 83 tiene pow(2, 4) = 16 números impares.

A continuación se muestra la implementación del enfoque anterior: 

   
// 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 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.

# 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# 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 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.
?>

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

4

Complejidad temporal: O(L), donde L es la longitud de una representación binaria de un N dado. 

Complejidad espacial: O(1)