Cuente los coeficientes binomiales pares e impares de N-ésima potencia

Dado un número entero N , la tarea es contar el número de coeficientes binomiales pares e impares hasta N ^-ésima potencia.

Ejemplos:

Entrada: N = 4
Salida:
Impar: 2
Par: 3
Explicación:
Los coeficientes binomiales son los siguientes:
⁴ C ₀ = 1, ⁴ C ₁ = 4, ⁴ C ₂ = 6, ⁴ C ₃ = 4, ⁴ C ₄ = 1.
Por tanto, se puede observar que existen exactamente 2 Coeficientes Binomiales pares y 3 impares.

Entrada: N = 5
Salida:
Impar: 4
Par: 2
Explicación:
Los coeficientes binomiales son los siguientes:
⁵ C ₀ = 1, ⁵ C ₁ = 5, ⁵ C ₂ = 10, ⁵ C ₃ = 10, ⁵ C ₄ = 5, ⁵ C ₅ = 1.
Por lo tanto, hay 4 coeficientes impares y 2 pares.

Enfoque de la solución: la idea para resolver este problema es utilizar la manipulación de bits . Encuentre los bits establecidos en el entero N dado . El recuento de coeficientes binomiales impares es igual a 2 ^ El recuento de bits establecidos en N . De manera similar, el recuento de coeficientes binomiales pares es igual a (N + 1 – 2 ^ Count of Set Bits in N) .

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

// C++ program for the above approach
 
#include <iostream>
#include <math.h>
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 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 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# 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

<script>
 
// Javascript program for the above approach
 
// Function to count set bits in
// binary representation of number N
function countSetBits(N)
{
    let count = 0;
  
    // Count set bits in N
    while (N != 0)
    {
        N = N & (N - 1);
        count++;
    }
  
    // Return the final count
    return count;
}
   
// Driver Code
let N = 4;
 
let bits = countSetBits(N);
 
// Print odd Binomial coefficients
document.write("Odd " + ": " +
              (Math.pow(2, bits)) + "<br/>");
 
// Print even Binomial coefficients
document.write("Even " + ": " +
              (N + 1 - (Math.pow(2, bits))));
               
// This code is contributed by splevel62
 
</script>

Odd : 2
Even : 3

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)