Cuente el número de strings binarias de longitud N que tienen solo 0 y 1

Dado un número entero N , la tarea es contar el número de strings binarias de longitud N que tienen solo 0 y 1. 
Nota: Dado que el conteo puede ser muy grande, devuelva la respuesta módulo 10^9+7.

Ejemplos:  

Entrada:
Salida:
Explicación: Los números son 00, 01, 11, 10. Por lo tanto, la cuenta es 4.

Entrada:
Salida:
Explicación: Los números son 000, 001, 011, 010, 111, 101, 110, 100. Por lo tanto, la cuenta es 8. 
 

Enfoque: El problema se puede resolver fácilmente usando Permutación y Combinación. En cada posición de la string solo puede haber dos posibilidades, es decir, 0 o 1. Por lo tanto, el número total de permutaciones de 0 y 1 en una string de longitud N viene dado por 2*2*2*…(N veces) , es decir, 2^N. La respuesta puede ser muy grande, por lo que se devuelve módulo por 10^9+7.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
 
// Iterative Function to calculate (x^y)%p in O(log y)
ll power(ll x, ll y, ll p)
{
    ll res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function to count the number of binary
// strings of length N having only 0's and 1's
ll findCount(ll N)
{
    int count = power(2, N, mod);
    return count;
}
 
// Driver code
int main()
{
    ll N = 25;
 
    cout << findCount(N);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
static int mod = (int) (1e9 + 7);
 
// Iterative Function to calculate (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
    int res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0)
    {
 
        // If y is odd, multiply x with result
        if ((y & 1)==1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function to count the number of binary
// strings of length N having only 0's and 1's
static int findCount(int N)
{
    int count = power(2, N, mod);
    return count;
}
 
// Driver code
public static void main(String[] args)
{
        int N = 25;
        System.out.println(findCount(N));
}
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python 3 implementation of the approach
mod = 1000000007
 
# Iterative Function to calculate (x^y)%p in O(log y)
def power(x, y, p):
    res = 1 # Initialize result
 
    x = x % p # Update x if it is more than or
              # equal to p
 
    while (y > 0):
         
        # If y is odd, multiply x with result
        if (y & 1):
            res = (res * x) % p
 
        # y must be even now
        y = y >> 1 # y = y/2
        x = (x * x) % p
 
    return res
 
# Function to count the number of binary
# strings of length N having only 0's and 1's
def findCount(N):
    count = power(2, N, mod)
    return count
 
# Driver code
if __name__ == '__main__':
    N = 25
    print(findCount(N))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the above approach
using System;
 
class GFG
{
 
    static int mod = (int) (1e9 + 7);
     
    // Iterative Function to calculate (x^y)%p in O(log y)
    static int power(int x, int y, int p)
    {
        int res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        while (y > 0)
        {
     
            // If y is odd, multiply x with result
            if ((y & 1) == 1)
                res = (res * x) % p;
     
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
     
    // Function to count the number of binary
    // strings of length N having only 0's and 1's
    static int findCount(int N)
    {
        int count = power(2, N, mod);
        return count;
    }
     
    // Driver code
    public static void Main()
    {
            int N = 25;
            Console.WriteLine(findCount(N));
    }
}
 
// This code is contributed by Ryuga

PHP

<?php
// PHP implementation of the approach
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power($x, $y)
{
    $p = 1000000007;
    $res = 1; // Initialize result
 
    $x = $x % $p; // Update x if it is more
                  // than or equal to p
 
    while ($y > 0)
    {
 
        // If y is odd, multiply x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        $y = $y >> 1; // y = y/2
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
// Function to count the number of binary
// strings of length N having only 0's and 1's
function findCount($N)
{
    $count = power(2, $N);
    return $count;
}
 
// Driver code
$N = 25;
 
echo findCount($N);
     
// This code is contributed by Rajput-Ji
?>

Javascript

<script>
 
// Javascript implementation of the approach
mod = 1000000007
 
// Iterative Function to calculate
// (x^y)%p in O(log y)
function power(x, y, p)
{
     
    // Initialize result
    var res = 1;
     
    // Update x if it is more than or
    // equal to p
    x = x % p;
     
    while (y > 0)
    {
         
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function to count the number of binary
// strings of length N having only 0's and 1's
function findCount(N)
{
    var count = power(2, N, mod);
    return count;
}
 
// Driver code
var N = 25;
 
document.write(findCount(N));
 
// This code is contributed by noob2000
 
</script>
Producción: 

33554432

 

 Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *