'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List



class Solution:
    """
    @param x: a number
    @return: return the next sparse number behind x
    """
    
    def nextSparseNum1(self, x):
        x = '0' + bin(x)[2:] # pad '0' for string starting with "11"
        while True:
            try:
                i = x.index('011')
                x = x[:i] + '1' + '0'*(len(x) - i - 1)
            except:
                break
        return int(x, 2)
    
    
    def nextSparseNum(self, 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.  
        bins = []  
        while (x != 0): 
            bins.append(x & 1)  
            x >>= 1
      
        # There my be extra bit in result,  
        # so add one extra bit  
        bins.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 ((bins[i] == 1 and bins[i - 1] == 1 
                and bins[i + 1] != 1)): 
                      
                # Make the next bit 1 
                bins[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): 
                    bins[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 += bins[i] * (1 << i)  
        return ans  