Recuento de números cuyos bits 0 y N están establecidos

Dado un entero positivo N , la tarea es contar los números que se pueden representar con N ^bits y cuyos bits ⁰ y N están establecidos.

Ejemplos:

Entrada: N = 2 
Salida: 1 
Todos los enteros de 2 bits posibles son 00, 01, 10 y 11. 
De los cuales solo 11 tiene 0 y N ^{bits establecidos} .
Entrada: N = 4 
Salida: 4  

Enfoque: De los N bits dados, solo se deben configurar dos bits, es decir, el bit ⁰ y el ^bit N. Entonces, al configurar estos 2 bits como 1, nos quedamos con el resto N – 2 bits, cada uno de los cuales puede ser 0 o 1 y hay 2 ^{N – 2} formas de hacerlo.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of n-bit
// numbers whose 0th and nth bits are set
int countNum(int n)
{
    if (n == 1)
        return 1;
    int count = pow(2, n - 2);
    return count;
}
 
// Driver code
int main()
{
    int n = 3;
    cout << countNum(n);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
    // Function to return the count of n-bit
    // numbers whose 0th and nth bits are set
    static int countNum(int n)
    {
        if (n == 1)
            return 1;
             
        int count = (int) Math.pow(2, n - 2);
        return count;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 3;
        System.out.println(countNum(n));
    }
}
 
// This code is contributed by ajit

# Python3 implementation of the approach
 
# Function to return the count of n-bit
# numbers whose 0th and nth bits are set
def countNum(n):
    if (n == 1):
        return 1
    count = pow(2, n - 2)
    return count
 
# Driver code
 
n = 3
print(countNum(n))
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the count of n-bit
    // numbers whose 0th and nth bits are set
    static int countNum(int n)
    {
        if (n == 1)
            return 1;
             
        int count = (int) Math.Pow(2, n - 2);
        return count;
    }
     
    // Driver code
    static public void Main ()
    {
        int n = 3;
        Console.WriteLine(countNum(n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript implementation of the approach
 
// Function to return the count of n-bit
// numbers whose 0th and nth bits are set
function countNum(n)
{
    if (n == 1)
        return 1;
    let count = Math.pow(2, n - 2);
    return count;
}
 
// Driver code
    let n = 3;
    document.write(countNum(n));
 
</script>

2

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)