Find Next Sparse Number | Java program to find next sparse number ; 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 . ; 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 . get ( ] ; Driver program
import java . util . * ; class GFG { static int nextSparse ( int x ) { ArrayList < Integer > bin = new ArrayList < Integer > ( ) ; while ( x != 0 ) { bin . add ( x & 1 ) ; x >>= 1 ; } bin . add ( 0 ) ; int last_final = 0 ; for ( int i = 1 ; i < n - 1 ; i ++ ) { if ( bin . get ( i ) == 1 && bin . get ( i - 1 ) == 1 && bin . get ( i + 1 ) != 1 ) { bin . set ( i + 1 , 1 ) ; for ( int j = i ; j >= last_final ; j -- ) bin . set ( j , 0 ) ; last_final = i + 1 ; } } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) ans += bin . get ( i ) * ( 1 << i ) ; return ans ; } public static void main ( String [ ] args ) { int x = 38 ; System . out . println ( " Next ▁ Sparse ▁ Number ▁ is ▁ " + nextSparse ( x ) ) ; } }