Count of divisors having more set bits than quotient on dividing N | Return the count of set bit . ; check if q and d have same number of set bit . ; Binary Search to find the point at which number of set in q is less than or equal to d . ; while left index is less than right index ; finding the middle . ; check if q and d have same number of set it or not . ; Driver Code
function bit ( x ) { let ans = 0 ; while ( x > 0 ) { x = parseInt ( x / 2 , 10 ) ; ans ++ ; } return ans ; } function check ( d , x ) { if ( bit ( parseInt ( x / d , 10 ) ) <= bit ( d ) ) return true ; return false ; } function bs ( n ) { let l = 1 , r = Math . sqrt ( n ) ; while ( l < r ) { let m = parseInt ( ( l + r ) / 2 , 10 ) ; if ( check ( m , n ) ) r = m ; else l = m + 1 ; } if ( ! check ( l , n ) ) return l + 1 ; else return l ; } function countDivisor ( n ) { return n - bs ( n ) + 1 ; } let n = 5 ; document . write ( countDivisor ( n ) ) ;