Find next greater element with no consecutive 1 in it 's binary representation | JavaScript implementation of the approach ; To store the pre - computed integers ; Function that returns true if the binary representation of x contains consecutive 1 s ; To store the previous bit ; Check whether the previous bit and the current bit are both 1 ; Update previous bit ; Go to the next bit ; Function to pre - compute the valid numbers from 0 to MAX ; Store all the numbers which do not have consecutive 1 s ; Function to return the minimum number greater than n which does not contain consecutive 1 s ; Search for the next greater element with no consecutive 1 s ; Function to perform the queries ; Driver code ; Pre - compute the numbers ; Perform the queries
const MAX = 100000 ; let v = [ ] ; function upper_bound ( ar , k ) { let s = 0 ; let e = ar . length ; while ( s != e ) { let mid = s + e >> 1 ; if ( ar [ mid ] <= k ) { s = mid + 1 ; } else { e = mid ; } } if ( s == ar . length ) { return - 1 ; } return s ; } function consecutiveOnes ( x ) { let p = 0 ; while ( x > 0 ) { if ( x % 2 == 1 && p == 1 ) return true ; p = x % 2 ; x = parseInt ( x / 2 ) ; } return false ; } function preCompute ( ) { for ( let i = 0 ; i <= MAX ; i ++ ) { if ( ! consecutiveOnes ( i ) ) v . push ( i ) ; } } function nextValid ( n ) { let it = upper_bound ( v , n ) ; let val = v [ it ] ; return val ; } function performQueries ( queries , q ) { for ( let i = 0 ; i < q ; i ++ ) document . write ( nextValid ( queries [ i ] ) + " " ) ; } let queries = [ 4 , 6 ] ; let q = queries . length ; preCompute ( ) ; performQueries ( queries , q ) ;