Find Next Sparse Number | PHP 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
< ? php function nextSparse ( $ x ) { $ bin = array ( ) ; while ( $ x != 0 ) { array_push ( $ bin , $ x & 1 ) ; $ x >>= 1 ; } array_push ( $ bin , 0 ) ; $ last_final = 0 ; for ( $ i = 1 ; $ i < $ n - 1 ; $ i ++ ) { if ( $ bin [ $ i ] == 1 && $ bin [ $ i - 1 ] == 1 && $ bin [ $ i + 1 ] != 1 ) { $ bin [ $ i + 1 ] = 1 ; for ( $ j = $ i ; $ j >= $ last_final ; $ j -- ) $ bin [ $ j ] = 0 ; $ last_final = $ i + 1 ; } } $ ans = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ ans += $ bin [ $ i ] * ( 1 << $ i ) ; return $ ans ; } $ x = 38 ; echo " Next ▁ Sparse ▁ Number ▁ is ▁ " . nextSparse ( $ x ) ; ? >