Find Next Sparse Number | Javascript 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 ; Size of binary representation ; 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
function nextSparse ( x ) { let bin = new Array ( ) ; while ( x != 0 ) { bin . push ( x & 1 ) ; x >>= 1 ; } bin . push ( 0 ) ; n = bin . length ; let last_final = 0 ; for ( let i = 1 ; i < n - 1 ; i ++ ) { if ( bin [ i ] == 1 && bin [ i - 1 ] == 1 && bin [ i + 1 ] != 1 ) { bin [ i + 1 ] = 1 ; for ( let j = i ; j >= last_final ; j -- ) bin [ j ] = 0 ; last_final = i + 1 ; } } let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) ans += bin [ i ] * ( 1 << i ) ; return ans ; } let x = 38 ; document . write ( " " + nextSparse ( x ) ) ;