Números fibbinarios (sin 1 consecutivos en binario)

Dado N, compruebe si el número es un número fibbinario o no. Los números fibbinarios son números enteros cuya representación binaria no incluye números consecutivos. 

Ejemplos: 

Input : 10
Output : YES
Explanation: 1010 is the binary representation 
             of 10 which does not contains any 
             consecutive 1's.

Input : 11
Output : NO
Explanation: 1011 is the binary representation 
             of 11, which contains consecutive 
             1's 

La idea de hacer esto es desplazar el número a la derecha, hasta que n!=0. Para cada representación binaria de 1, verifique si el último bit encontrado fue 1 o no. Obtenga el último bit de representación binaria del entero haciendo a(n&1). Si el último bit de la representación binaria es 1 y el bit anterior antes de hacer un desplazamiento a la derecha también era uno, nos encontramos con unos consecutivos. Entonces llegamos a la conclusión de que no es un número ficticio. 
Algunos de los primeros números fibbinarios son:  

0, 2, 4, 8, 10, 16, 18, 20.......

CPP

// CPP program to check if a number
// is fibinnary number or not
#include <iostream>
using namespace std;
 
// function to check if binary
// representation of an integer
// has consecutive 1s
bool checkFibinnary(int n)
{
    // stores the previous last bit
    // initially as 0
    int prev_last = 0;
    
    while (n)
    {
        // if current last bit and
        // previous last bit is 1
        if ((n & 1) && prev_last)
            return false;
     
        // stores the last bit
        prev_last = n & 1;
     
        // right shift the number
        n >>= 1;
    }
 
    return true;
}
 
// Driver code to check above function
int main()
{
    int n = 10;
    if (checkFibinnary(n))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

Java

// Java program to check if a number
// is fibinnary number or not
class GFG {
     
    // function to check if binary
    // representation of an integer
    // has consecutive 1s
    static boolean checkFibinnary(int n)
    {
 
        // stores the previous last bit
        // initially as 0
        int prev_last = 0;
         
        while (n != 0)
        {
             
            // if current last bit and
            // previous last bit is 1
            if ((n & 1) != 0 && prev_last != 0)
             
                return false;
         
            // stores the last bit
            prev_last = n & 1;
         
            // right shift the number
            n >>= 1;
        }
     
        return true;
    }
     
    // Driver code to check above function
    public static void main(String[] args)
    {
        int n = 10;
 
        if (checkFibinnary(n) == true)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

Python3

# Python 3 program to check if a
# number is fibinnary number or
# not
 
# function to check if binary
# representation of an integer
# has consecutive 1s
def checkFibinnary(n):
 
    # stores the previous last bit
    # initially as 0
    prev_last = 0
     
    while (n):
     
        # if current last bit and
        # previous last bit is 1
        if ((n & 1) and prev_last):
            return False
     
        # stores the last bit
        prev_last = n & 1
     
        # right shift the number
        n >>= 1
     
 
    return True
 
# Driver code
n = 10
 
if (checkFibinnary(n)):
    print("YES")
else:
    print("NO")
 
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to check if a number
// is fibinnary number or not
using System;
 
class GFG {
     
    // function to check if binary
    // representation of an integer
    // has consecutive 1s
    static bool checkFibinnary(int n)
    {
 
        // stores the previous last bit
        // initially as 0
        int prev_last = 0;
         
        while (n != 0)
        {
             
            // if current last bit and
            // previous last bit is 1
            if ((n & 1) != 0 && prev_last != 0)
             
                return false;
         
            // stores the last bit
            prev_last = n & 1;
         
            // right shift the number
            n >>= 1;
        }
     
        return true;
    }
     
    // Driver code to check above function
    public static void Main()
    {
        int n = 10;
 
        if (checkFibinnary(n) == true)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to check if a number
// is fibinnary number or not
 
// function to check if binary
// representation of an integer
// has consecutive 1s
function checkFibinnary($n)
{
    // stores the previous last bit
    // initially as 0
    $prev_last = 0;
     
    while ($n)
    {
        // if current last bit and
        // previous last bit is 1
        if (($n & 1) && $prev_last)
            return false;
     
        // stores the last bit
        $prev_last = $n & 1;
     
        // right shift the number
        $n >>= 1;
    }
    return true;
}
 
// Driver code
$n = 10;
if (checkFibinnary($n))
    echo "YES";
else
    echo "NO";
 
// This code is contributed by mits
?>

Javascript

<script>
    // javascript program to check if a number
    // is fibinnary number or not   
    // function to check if binary
    // representation of an integer
    // has consecutive 1s
    function checkFibinnary(n) {
 
        // stores the previous last bit
        // initially as 0
        var prev_last = 0;
 
        while (n != 0) {
 
            // if current last bit and
            // previous last bit is 1
            if ((n & 1) != 0 && prev_last != 0)
 
                return false;
 
            // stores the last bit
            prev_last = n & 1;
 
            // right shift the number
            n >>= 1;
        }
 
        return true;
    }
 
    // Driver code to check above function
     
    var n = 10;
 
    if (checkFibinnary(n) == true)
        document.write("YES");
    else
        document.write("NO");
 
// This code contributed by Rajput-Ji
</script>

Producción:  

YES

Complejidad de tiempo : O (logN), ya que estamos usando un bucle para atravesar logN veces, estamos disminuyendo por división de piso de 2 (ya que desplazar un número a la derecha por 1 es equivalente a dividir el piso por 2) en cada iteración, por lo tanto, el ciclo itera registroN veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.

Números ficticios (sin 1 consecutivos en binario) – Enfoque O(1)
 

Publicación traducida automáticamente

Artículo escrito por Striver 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 *