Recuento de strings binarias de longitud dada que consta de al menos un 1

Dado un número entero N , la tarea es imprimir el número de strings binarias de longitud N que tienen al menos un ‘1’.

Ejemplos:  

Entrada: 2 
Salida: 3 
Explicación: 
“01”, “10” y “11” son las strings posibles

Entrada: 3 
Salida: 7 
Explicación: 
“001”, “011”, “010”, “100”, “101”, “110” y “111” son las strings posibles 
 

Enfoque: 
Podemos observar que: 

Solo una string de longitud N no contiene ningún 1, la llena solo con 0. 
Como son posibles 2 ^N strings de longitud N, la respuesta requerida es 2 ^N – 1 . 
 

Siga los pasos a continuación para resolver el problema: 

• Inicializar X = 1.
• Calcule hasta 2 ^N realizando un desplazamiento a la izquierda bit a bit en X, N-1 veces.
• Finalmente, imprima X – 1 como la respuesta requerida.

A continuación se muestra la implementación de nuestro enfoque: 

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// the count of strings
long count_strings(long n)
{
    int x = 1;
 
    // Calculate pow(2, n)
    for (int i = 1; i < n; i++) {
        x = (1 << x);
    }
 
    // Return pow(2, n) - 1
    return x - 1;
}
 
// Driver Code
int main()
{
    long n = 3;
 
    cout << count_strings(n);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to return
// the count of Strings
static long count_Strings(long n)
{
    int x = 1;
 
    // Calculate Math.pow(2, n)
    for(int i = 1; i < n; i++)
    {
       x = (1 << x);
    }
 
    // Return Math.pow(2, n) - 1
    return x - 1;
}
 
// Driver Code
public static void main(String[] args)
{
    long n = 3;
 
    System.out.print(count_Strings(n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to return
# the count of Strings
def count_Strings(n):
     
    x = 1;
 
    # Calculate pow(2, n)
    for i in range(1, n):
        x = (1 << x);
 
    # Return pow(2, n) - 1
    return x - 1;
 
# Driver Code
if __name__ == '__main__':
     
    n = 3;
 
    print(count_Strings(n));
 
# This code is contributed by Princi Singh

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to return
// the count of Strings
static long count_Strings(long n)
{
    int x = 1;
 
    // Calculate Math.Pow(2, n)
    for(int i = 1; i < n; i++)
    {
       x = (1 << x);
    }
     
    // Return Math.Pow(2, n) - 1
    return x - 1;
}
 
// Driver Code
public static void Main(String[] args)
{
    long n = 3;
 
    Console.Write(count_Strings(n));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to return
    // the count of Strings
    function count_Strings(n)
    {
        var x = 1;
 
        // Calculate Math.pow(2, n)
        for (i = 1; i < n; i++) {
            x = (1 << x);
        }
 
        // Return Math.pow(2, n) - 1
        return x - 1;
    }
 
    // Driver Code
     
        var n = 3;
 
        document.write(count_Strings(n));
 
// This code is contributed by todaysgaurav
 
</script>

3

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