Buscar el siguiente número disperso

Un número es Escaso si no hay dos 1 adyacentes en su representación binaria. Por ejemplo, 5 (representación binaria: 101) es escaso, pero 6 (representación binaria: 110) no es escaso. 
Dado un número x, encuentre el número disperso más pequeño que sea mayor o igual que x.

Ejemplos: 

Input: x = 6
Output: Next Sparse Number is 8

Input: x = 4
Output: Next Sparse Number is 4

Input: x = 38
Output: Next Sparse Number is 40

Input: x = 44
Output: Next Sparse Number is 64

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Una solución simple es hacer lo siguiente:  

1) Write a utility function isSparse(x) that takes a number 
   and returns true if x is sparse, else false.  This function
   can be easily written by traversing the bits of input number.
2) Start from x and do following 
   while(1)
   {
      if (isSparse(x))
         return x;
      else 
         x++
   }

La complejidad temporal de isSparse() es O(Log x). La complejidad temporal de esta solución es O(x Log x). El siguiente número disperso puede estar a una distancia máxima de O(x).
Gracias a kk_angel por sugerir la solución anterior.

Una solución eficiente puede resolver este problema sin verificar todos los números uno por uno. A continuación se muestran los pasos. 

1) Find binary of the given number and store it in a 
   boolean array.
2) Initialize last_finalized bit position as 0.
2) Start traversing the binary from least significant bit.
    a) If we get two adjacent 1's such that next (or third) 
       bit is not 1, then 
          (i)  Make all bits after this 1 to last finalized
               bit (including last finalized) as 0. 
          (ii) Update last finalized bit as next bit. 

Por ejemplo, si la representación binaria es 010100010 11 101, la cambiamos a 01010001 100000 (todos los bits después del resaltado 11 se establecen en 0). Nuevamente, dos 1 son adyacentes, así que cambie la representación binaria a 010100 10000000 . Esta es nuestra respuesta final.

A continuación se muestra la implementación de la solución anterior.  

// C++ program to find next sparse number
#include<bits/stdc++.h>
using namespace std;
 
int nextSparse(int x)
{
    // Find binary representation of x and store it in bin[].
    // bin[0] contains least significant bit (LSB), next
    // bit is in bin[1], and so on.
    vector<bool> bin;
    while (x != 0)
    {
        bin.push_back(x&1);
        x >>= 1;
    }
 
    // There my be extra bit in result, so add one extra bit
    bin.push_back(0);
    int n = bin.size();  // Size of binary representation
 
    // The position till which all bits are finalized
    int last_final = 0;
 
    // Start from second bit (next to LSB)
    for (int i=1; i<n-1; i++)
    {
       // If current bit and its previous bit are 1, but next
       // bit is not 1.
       if (bin[i] == 1 && bin[i-1] == 1 && bin[i+1] != 1)
       {
            // Make the next bit 1
            bin[i+1] = 1;
 
            // Make all bits before current bit as 0 to make
            // sure that we get the smallest next number
            for (int j=i; j>=last_final; j--)
                bin[j] = 0;
 
            // Store position of the bit set so that this bit
            // and bits before it are not changed next time.
            last_final = i+1;
        }
    }
 
    // Find decimal equivalent of modified bin[]
    int ans = 0;
    for (int i =0; i<n; i++)
        ans += bin[i]*(1<<i);
    return ans;
}
 
// Driver program
int main()
{
    int x = 38;
    cout << "Next Sparse Number is " << nextSparse(x);
    return 0;
}

// Java program to find next sparse number
import java.util.*;
 
class GFG{
static int nextSparse(int x)
{
    // Find binary representation of x and store it in bin.get(].
    // bin.get(0] contains least significant bit (LSB), next
    // bit is in bin.get(1], and so on.
    ArrayList<Integer> bin = new ArrayList<Integer>();
    while (x != 0)
    {
        bin.add(x&1);
        x >>= 1;
    }
 
    // There my be extra bit in result, so add one extra bit
    bin.add(0);
    int n = bin.size(); // Size of binary representation
 
    // The position till which all bits are finalized
    int last_final = 0;
 
    // Start from second bit (next to LSB)
    for (int i=1; i<n-1; i++)
    {
    // If current bit and its previous bit are 1, but next
    // bit is not 1.
    if (bin.get(i) == 1 && bin.get(i-1) == 1 && bin.get(i+1) != 1)
    {
            // Make the next bit 1
            bin.set(i+1,1);
 
            // Make all bits before current bit as 0 to make
            // sure that we get the smallest next number
            for (int j=i; j>=last_final; j--)
                bin.set(j,0);
 
            // Store position of the bit set so that this bit
            // and bits before it are not changed next time.
            last_final = i+1;
        }
    }
 
    // Find decimal equivalent of modified bin.get(]
    int ans = 0;
    for (int i =0; i<n; i++)
        ans += bin.get(i)*(1<<i);
    return ans;
}
 
// Driver program
public static void main(String[] args)
{
    int x = 38;
    System.out.println("Next Sparse Number is "+nextSparse(x));
}
}
// This code is contributed by mits

# Python3 program to find next
# sparse number
 
def nextSparse(x):
     
    # Find binary representation of
    # x and store it in bin[].
    # bin[0] contains least significant
    # bit (LSB), next bit is in bin[1],
    # and so on.
    bin = []
    while (x != 0):
        bin.append(x & 1)
        x >>= 1
 
    # There my be extra bit in result,
    # so add one extra bit
    bin.append(0)
    n = len(bin) # Size of binary representation
     
    # The position till which all
    # bits are finalized
    last_final = 0
 
    # Start from second bit (next to LSB)
    for i in range(1,n - 1):
         
        # If current bit and its previous
        # bit are 1, but next bit is not 1.
        if ((bin[i] == 1 and bin[i - 1] == 1
            and bin[i + 1] != 1)):
                 
            # Make the next bit 1
            bin[i + 1] = 1
             
            # Make all bits before current
            # bit as 0 to make sure that
            # we get the smallest next number
            for j in range(i,last_final-1,-1):
                bin[j] = 0
             
            # Store position of the bit set
            # so that this bit and bits
            # before it are not changed next time.
            last_final = i + 1
 
    # Find decimal equivalent
    # of modified bin[]
    ans = 0
    for i in range(n):
        ans += bin[i] * (1 << i)
    return ans
 
# Driver Code
if __name__=='__main__':
    x = 38
    print("Next Sparse Number is",nextSparse(x))
 
# This code is contributed by
# mits

// C# program to find next sparse number
using System;
using System.Collections;
 
 
class GFG{
static int nextSparse(int x)
{
    // Find binary representation of x and store it in bin.get(].
    // bin.get(0] contains least significant bit (LSB), next
    // bit is in bin.get(1], and so on.
    ArrayList bin = new ArrayList();
    while (x != 0)
    {
        bin.Add(x&1);
        x >>= 1;
    }
 
    // There my be extra bit in result, so add one extra bit
    bin.Add(0);
    int n = bin.Count; // Size of binary representation
 
    // The position till which all bits are finalized
    int last_final = 0;
 
    // Start from second bit (next to LSB)
    for (int i = 1; i < n-1; i++)
    {
    // If current bit and its previous bit are 1, but next
    // bit is not 1.
    if ((int)bin[i] == 1 && (int)bin[i-1] == 1 && (int)bin[i+1] != 1)
    {
            // Make the next bit 1
            bin[i+1]=1;
 
            // Make all bits before current bit as 0 to make
            // sure that we get the smallest next number
            for (int j = i; j >= last_final; j--)
                bin[j]=0;
 
            // Store position of the bit set so that this bit
            // and bits before it are not changed next time.
            last_final = i + 1;
        }
    }
 
    // Find decimal equivalent of modified bin.get(]
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += (int)bin[i]*(1<<i);
    return ans;
}
 
// Driver program
static void Main()
{
    int x = 38;
    Console.WriteLine("Next Sparse Number is "+nextSparse(x));
}
}
// This code is contributed by mits

<?php
// PHP program to find next sparse number
 
function nextSparse($x)
{
    // Find binary representation of
    // x and store it in bin[].
    // bin[0] contains least significant
    // bit (LSB), next bit is in bin[1],
    // and so on.
    $bin = array();
    while ($x != 0)
    {
        array_push($bin, $x & 1);
        $x >>= 1;
    }
 
    // There my be extra bit in result,
    // so add one extra bit
    array_push($bin, 0);
    $n = count($bin); // Size of binary representation
     
    // The position till which all
    // bits are finalized
    $last_final = 0;
 
    // Start from second bit (next to LSB)
    for ($i = 1; $i < $n - 1; $i++)
    {
    // If current bit and its previous
    // bit are 1, but next bit is not 1.
    if ($bin[$i] == 1 &&
        $bin[$i - 1] == 1 &&
        $bin[$i + 1] != 1)
    {
        // Make the next bit 1
        $bin[$i + 1] = 1;
 
        // Make all bits before current
        // bit as 0 to make sure that
        // we get the smallest next number
        for ($j = $i; $j >= $last_final; $j--)
            $bin[$j] = 0;
 
        // Store position of the bit set
        // so that this bit and bits
        // before it are not changed next time.
        $last_final = $i + 1;
    }
    }
 
    // Find decimal equivalent
    // of modified bin[]
    $ans = 0;
    for ($i = 0; $i < $n; $i++)
        $ans += $bin[$i] * (1 << $i);
    return $ans;
}
 
// Driver Code
$x = 38;
echo "Next Sparse Number is " .
                nextSparse($x);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to find next sparse number
function nextSparse(x)
{
     
    // Find binary representation of
    // x and store it in bin[].
    // bin[0] contains least significant
    // bit (LSB), next bit is in bin[1],
    // and so on.
    let bin = new Array();
    while (x != 0)
    {
        bin.push(x & 1);
        x >>= 1;
    }
 
    // There my be extra bit in result,
    // so add one extra bit
    bin.push(0);
     
    // Size of binary representation
    n = bin.length;
     
    // The position till which all
    // bits are finalized
    let last_final = 0;
 
    // Start from second bit (next to LSB)
    for(let i = 1; i < n - 1; i++)
    {
         
        // If current bit and its previous
        // bit are 1, but next bit is not 1.
        if (bin[i] == 1 &&
            bin[i - 1] == 1 &&
            bin[i + 1] != 1)
        {
             
            // Make the next bit 1
            bin[i + 1] = 1;
     
            // Make all bits before current
            // bit as 0 to make sure that
            // we get the smallest next number
            for(let j = i; j >= last_final; j--)
                bin[j] = 0;
     
            // Store position of the bit set
            // so that this bit and bits
            // before it are not changed next time.
            last_final = i + 1;
        }
    }
 
    // Find decimal equivalent
    // of modified bin[]
    let ans = 0;
    for(let i = 0; i < n; i++)
        ans += bin[i] * (1 << i);
         
    return ans;
}
 
// Driver Code
let x = 38;
document.write("Next Sparse Number is " +
               nextSparse(x));
                
// This code is contributed by gfgking
 
</script>

Producción: 

Next Sparse Number is 40

La complejidad temporal de esta solución es O(Log x).

Espacio auxiliar: O (log x)
Gracias a gccode por sugerir la solución anterior. 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.