Contar strings con 1 consecutivos

Dado un número n, cuente el número de strings de longitud n con 1 consecutivos en ellas.

Ejemplos: 

Input  : n = 2
Output : 1
There are 4 strings of length 2, the
strings are 00, 01, 10 and 11. Only the 
string 11 has consecutive 1's.

Input  : n = 3
Output : 3
There are 8 strings of length 3, the
strings are 000, 001, 010, 011, 100, 
101, 110 and 111.  The strings with
consecutive 1's are 011, 110 and 111.

Input : n = 5
Output : 19

El problema inverso de contar strings sin 1 consecutivos se puede resolver mediante Programación Dinámica (Vea la solución aquí ). Podemos usar esa solución y encontrar el conteo requerido siguiendo los pasos a continuación.

1. Calcule el número de strings binarias sin 1 consecutivos usando el enfoque que se describe aquí . Sea esta cuenta c .
2. El recuento de todas las strings binarias posibles de longitud n es 2^n.
3. El total de strings binarias con 1 consecutivo es 2^n – c.

A continuación se muestra la implementación de los pasos anteriores. 

// C++ program to count all distinct
// binary strings with two consecutive 1's
#include <iostream>
using namespace std;
 
// Returns count of n length binary
// strings with consecutive 1's
int countStrings(int n)
{
    // Count binary strings without consecutive 1's.
    // See the approach discussed on be
    // ( http://goo.gl/p8A3sW )
    int a[n], b[n];
    a[0] = b[0] = 1;
    for (int i = 1; i < n; i++)
    {
        a[i] = a[i - 1] + b[i - 1];
        b[i] = a[i - 1];
    }
 
    // Subtract a[n-1]+b[n-1] from 2^n
    return (1 << n) - a[n - 1] - b[n - 1];
}
 
// Driver code
int main()
{
    cout << countStrings(5) << endl;
    return 0;
}

// Java program to count all distinct
// binary strings with two consecutive 1's
 
class GFG {
 
    // Returns count of n length binary
    // strings with consecutive 1's
    static int countStrings(int n)
    {
        // Count binary strings without consecutive 1's.
        // See the approach discussed on be
        // ( http://goo.gl/p8A3sW )
        int a[] = new int[n], b[] = new int[n];
        a[0] = b[0] = 1;
 
        for (int i = 1; i < n; i++) {
            a[i] = a[i - 1] + b[i - 1];
            b[i] = a[i - 1];
        }
 
        // Subtract a[n-1]+b[n-1]
        from 2 ^ n return (1 << n) - a[n - 1] - b[n - 1];
    }
 
    // Driver code
    public static void main(String args[])
    {
        System.out.println(countStrings(5));
    }
}
 
// This code is contributed by Nikita tiwari.

# Python 3 program to count all
# distinct binary strings with
# two consecutive 1's
 
 
# Returns count of n length
# binary strings with
# consecutive 1's
def countStrings(n):
 
    # Count binary strings without
    # consecutive 1's.
    # See the approach discussed on be
    # ( http://goo.gl/p8A3sW )
    a = [0] * n
    b = [0] * n
    a[0] = b[0] = 1
    for i in range(1, n):
        a[i] = a[i - 1] + b[i - 1]
        b[i] = a[i - 1]
 
    # Subtract a[n-1]+b[n-1] from 2^n
    return (1 << n) - a[n - 1] - b[n - 1]
 
 
# Driver code
print(countStrings(5))
 
 
# This code is contributed
# by Nikita tiwari.

// program to count all distinct
// binary strings with two
// consecutive 1's
using System;
 
class GFG {
 
    // Returns count of n length
    // binary strings with
    // consecutive 1's
    static int countStrings(int n)
    {
        // Count binary strings without
        // consecutive 1's.
        // See the approach discussed on
        // ( http://goo.gl/p8A3sW )
        int[] a = new int[n];
        int[] b = new int[n];
        a[0] = b[0] = 1;
 
        for (int i = 1; i < n; i++)
        {
            a[i] = a[i - 1] + b[i - 1];
            b[i] = a[i - 1];
        }
 
        // Subtract a[n-1]+b[n-1]
        // from 2^n
        return (1 << n) - a[n - 1] - b[n - 1];
    }
 
    // Driver code
    public static void Main()
    {
        Console.WriteLine(countStrings(5));
    }
}
 
// This code is contributed by Anant Agarwal.

<?php
// PHP program to count all
// distinct binary strings
// with two consecutive 1's
// Returns count of n length binary
// strings with consecutive 1's
 
function countStrings($n)
{
     
    // Count binary strings without consecutive 1's.
    // See the approach discussed on be
    // ( http://goo.gl/p8A3sW )
    $a[$n] = 0;
    $b[$n] = 0;
    $a[0] = $b[0] = 1;
    for ($i = 1; $i < $n; $i++)
    {
        $a[$i] = $a[$i - 1] + $b[$i - 1];
        $b[$i] = $a[$i - 1];
    }
 
    // Subtract a[n-1]+b[n-1] from 2^n
    return (1 << $n) - $a[$n - 1] -
                       $b[$n - 1];
}
 
    // Driver Code
    echo countStrings(5), "\n";
 
// This Code is contributed by Ajit
?>

<script>
 
// JavaScript program to count all distinct
// binary strings with two
// consecutive 1's
 
    // Returns count of n length binary
    // strings with consecutive 1's
    function countStrings(n)
    {
        // Count binary strings without consecutive 1's.
        // See the approach discussed on be
        // ( http://goo.gl/p8A3sW )
        let a = [], b = [];
        a[0] = b[0] = 1;
  
        for (let i = 1; i < n; i++) {
            a[i] = a[i - 1] + b[i - 1];
            b[i] = a[i - 1];
        }
  
        // Subtract a[n-1]+b[n-1]
        // from 2 ^ n
        return (1 << n) - a[n - 1] - b[n - 1];
    }
 
// Driver Code
 
       document.write(countStrings(5));
 
</script>

19

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)

Optimización: 
La complejidad temporal de la solución anterior es O(n). Podemos optimizar la solución anterior para que funcione en O (Iniciar sesión). 
Si echamos un vistazo más de cerca al patrón de contar strings sin unos consecutivos, podemos observar que la cuenta es en realidad (n+2) el ^número de Fibonacci para n >= 1. Los números de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ….

n = 1, count = 0  = 21 - fib(3) 
n = 2, count = 1  = 22 - fib(4)
n = 3, count = 3  = 23 - fib(5)
n = 4, count = 8  = 24 - fib(6)
n = 5, count = 19 = 25 - fib(7)
................

Podemos encontrar el n-ésimo número de Fibonacci en el tiempo O (Log n) (consulte el método 4 aquí ). 
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.