Contar pares de ceros consecutivos

Considere una secuencia que comienza con un 1 en una máquina. En cada paso sucesivo, la máquina transforma simultáneamente cada dígito 0 en la secuencia 10 y cada dígito 1 en la secuencia 01. 
Después del primer paso de tiempo, se obtiene la secuencia 01; después del segundo, la secuencia 1001, después del tercero, la secuencia 01101001 y así sucesivamente.
¿Cuántos pares de ceros consecutivos aparecerán en la secuencia después de n pasos?
Ejemplos: 
 

Input : Number of steps = 3
Output: 1
// After 3rd step sequence will be  01101001

Input : Number of steps = 4
Output: 3
// After 4rd step sequence will be 1001011001101001

Input : Number of steps = 5
Output: 5
// After 3rd step sequence will be  01101001100101101001011001101001

Este es un problema de razonamiento simple. Si observamos la secuencia con mucho cuidado, podremos encontrar un patrón para la secuencia dada. Si n=1 la secuencia será {01} entonces el número de pares de ceros consecutivos será 0, si n = 2 la secuencia será {1001} entonces el número de pares de ceros consecutivos será 1, si n=3 la secuencia será {01101001} entonces el número de pares de ceros consecutivos es 1, 
si n=4 la secuencia será {1001011001101001} entonces el número de pares de ceros consecutivos es 3.
Por lo tanto, la longitud de la secuencia siempre será una potencia de 2. Podemos ver después de la secuencia de longitud 12 se repite y tiene longitudes de 12. Y en un segmento de longitud 12, hay un total de 2 pares de ceros consecutivos. Por lo tanto, podemos generalizar el patrón dado q = (2^n/12) y el total de pares de ceros consecutivos será 2*q+1. 
 

// C++ program to find number of consecutive
// 0s in a sequence
#include<bits/stdc++.h>
using namespace std;
 
// Function to find number of consecutive Zero Pairs
// Here n is number of steps
int consecutiveZeroPairs(int n)
{
    // Base cases
    if (n==1)
        return 0;
    if (n==2 || n==3)
        return 1;
 
    // Calculating how many times divisible by 12, i.e.,
    // count total number repeating segments of length 12
    int q = (pow(2, n) / 12);
 
    // number of consecutive Zero Pairs
    return 2 * q + 1;
}
 
// Driver code
int main()
{
    int n = 5;
    cout << consecutiveZeroPairs(n) << endl;
    return 0;
}

//Java program to find number of
// consecutive 0s in a sequence
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Function to find number of consecutive
    // Zero Pairs. Here n is number of steps
    static int consecutiveZeroPairs(int n)
    {
        // Base cases
        if (n == 1)
            return 0;
        if (n == 2 || n == 3)
            return 1;
 
        // Calculating how many times divisible
        // by 12, i.e.,count total number
        // repeating segments of length 12
        int q = ((int)(Math.pow(2, n)) / 12);
 
        // number of consecutive Zero Pairs
        return (2 * q + 1);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 5;
        System.out.println(consecutiveZeroPairs(n));
    }
}
     
// This code is contributed by Nikita Tiwari.

# Python program to find number of
# consecutive 0s in a sequence
import math
 
# Function to find number of consecutive
# Zero Pairs. Here n is number of steps
def consecutiveZeroPairs(n) :
 
    # Base cases
    if (n == 1) :
        return 0
    if (n == 2 or n == 3) :
        return 1
 
    # Calculating how many times divisible
    # by 12, i.e.,count total number
    # repeating segments of length 12
    q =(int) (pow(2,n) / 12)
 
    # number of consecutive Zero Pairs
    return 2 * q + 1
 
# Driver code
n = 5
print (consecutiveZeroPairs(n))
 
#This code is contributed by Nikita Tiwari.

// C# program to find number of
// consecutive 0s in a sequence
using System;
 
class GFG {
     
    // Function to find number of
    // consecutive Zero Pairs.
    // Here n is number of steps
    static int consecutiveZeroPairs(int n)
    {
        // Base cases
        if (n == 1)
            return 0;
        if (n == 2 || n == 3)
            return 1;
 
        // Calculating how many times divisible
        // by 12, i.e.,count total number
        // repeating segments of length 12
        int q = ((int)(Math.Pow(2, n)) / 12);
 
        // number of consecutive Zero Pairs
        return (2 * q + 1);
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 5;
        Console.Write(consecutiveZeroPairs(n));
    }
}
     
// This code is contributed by Nitin mittal.

<?php
// PHP program to find number
// of consecutive 0s in a sequence
 
// Function to find number
// of consecutive Zero Pairs
// Here n is number of steps
function consecutiveZeroPairs($n)
{
    // Base cases
    if ($n == 1)
        return 0;
    if ($n == 2 || $n == 3)
        return 1;
 
    // Calculating how many times
    // divisible by 12, i.e., count
    // total number repeating segments
    // of length 12
    $q = floor(pow(2, $n) / 12);
 
    // number of consecutive Zero Pairs
    return 2 * $q + 1;
}
 
// Driver code
$n = 5;
echo consecutiveZeroPairs($n) ;
 
// This code is contributed
// by nitin mittal.
?>

<script>
//javascript program to find number of
// consecutive 0s in a sequence
 
    // Function to find number of consecutive
    // Zero Pairs. Here n is number of steps
    function consecutiveZeroPairs(n)
    {
        // Base cases
        if (n == 1)
            return 0;
        if (n == 2 || n == 3)
            return 1;
 
        // Calculating how many times divisible
        // by 12, i.e.,count total number
        // repeating segments of length 12
        var q =(parseInt((Math.pow(2, n)) / 12));
 
        // number of consecutive Zero Pairs
        return (2 * q + 1);
    }
 
    // Driver code
 
        var n = 5;
        document.write(consecutiveZeroPairs(n));
 
// This code is contributed by umadevi9616
</script>

Producción : 
 

5

Este artículo es una contribución de Shashank Mishra (Gullu) . este artículo está revisado por el equipo GeeksForGeeks. 
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.