Recuento de números enteros pares e impares de N bits con K bits establecidos

Dados dos enteros positivos N y K , la tarea es contar el número de enteros pares e impares que consisten en N bits, de los cuales se establecen K bits.

Ejemplos:

Entrada: N = 5, K = 2
Salida: 3 1
Explicación:
Los enteros pares de 5 bits que tienen 2 bits establecidos son: 10010(= 18), 10100(= 20), 11000(= 24). Entonces, el conteo es 3.
El entero impar de 5 bits que tiene 2 bits establecidos es 10001 (= 17). Entonces, el conteo es 1.

Entrada: N = 5, K = 5
Salida: 0 1

Enfoque: El problema dado se puede resolver usando las siguientes observaciones:

• Para cualquier número entero de N bits, el ^bit N (bit más significativo ) debe ser un bit establecido.
• Para que cualquier número entero de N bits sea impar, el primer ^bit (bit menos significativo ) debe ser un bit establecido.
• Para que cualquier número entero de N bits sea par, el primer ^bit (bit menos significativo) no debe ser un bit establecido.

Por lo tanto, el número de enteros pares se puede obtener fijando el N ^-ésimo bit como 1 y el 1.er ^bit como 0 y calculando el número de formas de ordenar los bits restantes. De manera similar, el número de enteros impares se puede obtener fijando el 1 ^er y el N ^th bit como 1 .

El número total de formas distintas de organizar X bits con Y bits establecidos viene dado por:

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
long long factorial(int n)
{
    long long ans = 1;
    while (n >= 1) {
        ans *= n;
        n--;
    }
    return ans;
}
 
// Function to find the count of odd and
// even integers having N bits and K
// set bits
void Binary_Num(int n, int k)
{
    long long num_even, num_odd;
   
    // Find the count of even integers
    if (n - k - 1 >= 0 && k - 1 >= 0) {
        num_even
            = factorial(n - 2)
              / (factorial(k - 1) * factorial(n - k - 1));
    }
    else {
        num_even = 0;
    }
 
    // Find the count of odd integers
    if (k - 2 >= 0) {
        num_odd = factorial(n - 2)
                  / (factorial(k - 2) * factorial(n - k));
    }
    else {
        num_odd = 0;
    }
    // Print the total count
    cout << num_even << " " << num_odd << endl;
}
 
// Driver code
int main()
{
 
    int N = 9, K = 6;
    Binary_Num(N, K);
    return 0;
}
 
// This code is contributed by maddler.

// Java program for the above approach
import java.io.*;
class GFG {
static long  factorial(int n)
{
    long  ans = 1;
    while (n >= 1) {
        ans *= n;
        n--;
    }
    return ans;
}
   
// Function to find the count of odd and
// even integers having N bits and K
// set bits
static void Binary_Num(int n, int k)
{
    long num_even, num_odd;
    
    // Find the count of even integers
    if (n - k - 1 >= 0 && k - 1 >= 0) {
        num_even
            = factorial(n - 2)
              / (factorial(k - 1) * factorial(n - k - 1));
    }
    else {
        num_even = 0;
    }
  
    // Find the count of odd integers
    if (k - 2 >= 0) {
        num_odd = factorial(n - 2)
                  / (factorial(k - 2) * factorial(n - k));
    }
    else {
        num_odd = 0;
    }
    // Print the total count
    System.out.println( num_even +" " +num_odd );
}
  
    // Driver Code
    public static void main(String[] args)
    {
         int N = 9, K = 6;
    Binary_Num(N, K);
    }
}
 
// This code is contributed by dwivediyash

# Python program for the above approach
 
import math
 
# Function to find the count of odd and
# even integers having N bits and K
# set bits
 
 
def Binary_Num(N, K):
 
    # Find the count of even integers
    if N-K-1 >= 0 and K-1 >= 0:
        num_even = math.factorial(
            N-2)/(math.factorial(K-1)
                  * math.factorial(N-K-1))
    else:
        num_even = 0
 
    # Find the count of odd integers
    if K-2 >= 0:
        num_odd = math.factorial(N-2) \
            / (math.factorial(K-2)
               * math.factorial(N-K))
    else:
        num_odd = 0
 
    # Print the total count
    print(int(num_even), int(num_odd))
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 9
    K = 6
 
    Binary_Num(N, K)

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static int factorial(int n)
{
    int ans = 1;
    while (n >= 1) {
        ans *= n;
        n--;
    }
    return ans;
}
 
// Function to find the count of odd and
// even integers having N bits and K
// set bits
static void Binary_Num(int n, int k)
{
    int num_even, num_odd;
   
    // Find the count of even integers
    if (n - k - 1 >= 0 && k - 1 >= 0) {
        num_even
            = factorial(n - 2)
              / (factorial(k - 1) * factorial(n - k - 1));
    }
    else {
        num_even = 0;
    }
 
    // Find the count of odd integers
    if (k - 2 >= 0) {
        num_odd = factorial(n - 2)
                  / (factorial(k - 2) * factorial(n - k));
    }
    else {
        num_odd = 0;
    }
    // Print the total count
    Console.Write(num_even + " " + num_odd);
}
 
// Driver code
public static void Main()
{
 
    int N = 9, K = 6;
    Binary_Num(N, K);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
        // JavaScript Program to implement
        // the above approach
 
        function factorial(n) {
            let ans = 1;
            while (n >= 1) {
                ans *= n;
                n--;
            }
            return ans;
        }
 
        // Function to find the count of odd and
        // even integers having N bits and K
        // set bits
        function Binary_Num(n, k) {
            let num_even, num_odd;
 
            // Find the count of even integers
            if (n - k - 1 >= 0 && k - 1 >= 0) {
                num_even
                    = Math.floor(factorial(n - 2)
                        / (factorial(k - 1) * factorial(n - k - 1)));
            }
            else {
                num_even = 0;
            }
 
            // Find the count of odd integers
            if (k - 2 >= 0) {
                num_odd = Math.floor(factorial(n - 2)
                    / (factorial(k - 2) * factorial(n - k)));
            }
            else {
                num_odd = 0;
            }
             
            // Print the total count
            document.write(num_even + " " + num_odd + "<br>");
        }
 
        // Driver code
        let N = 9, K = 6;
        Binary_Num(N, K);
 
// This code is contributed by Potta Lokesh
    </script>

21 35

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Nota: Para consultas múltiples, calcule previamente los valores factoriales en una array que dará como resultado O(1) tiempo por consulta y O(N) para el cálculo previo.