Find Next Sparse Number | Python3 program to find next sparse number ; 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 . ; There my be extra bit in result , so add one extra bit ; The position till which all bits are finalized ; Start from second bit ( next to LSB ) ; If current bit and its previous bit are 1 , but next bit is not 1. ; Make the next bit 1 ; Make all bits before current bit as 0 to make sure that we get the smallest next number ; Store position of the bit set so that this bit and bits before it are not changed next time . ; Find decimal equivalent of modified bin [ ] ; Driver Code
def nextSparse ( x ) : NEW_LINE INDENT bin = [ ] NEW_LINE while ( x != 0 ) : NEW_LINE INDENT bin . append ( x & 1 ) NEW_LINE x >>= 1 NEW_LINE DEDENT bin . append ( 0 ) NEW_LINE last_final = 0 NEW_LINE for i in range ( 1 , n - 1 ) : NEW_LINE INDENT if ( ( bin [ i ] == 1 and bin [ i - 1 ] == 1 and bin [ i + 1 ] != 1 ) ) : NEW_LINE INDENT bin [ i + 1 ] = 1 NEW_LINE for j in range ( i , last_final - 1 , - 1 ) : NEW_LINE INDENT bin [ j ] = 0 NEW_LINE DEDENT last_final = i + 1 NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans += bin [ i ] * ( 1 << i ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT x = 38 NEW_LINE print ( " Next ▁ Sparse ▁ Number ▁ is " , nextSparse ( x ) ) NEW_LINE DEDENT