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
< ? php function bit ( $ x ) { $ ans = 0 ; while ( $ x ) { $ x /= 2 ; $ ans ++ ; } return $ ans ; } function check ( $ d , $ x ) { if ( bit ( $ x / $ d ) <= bit ( $ d ) ) return true ; return false ; } function bs ( int $ n ) { $ l = 1 ; $ r = sqrt ( $ n ) ; while ( $ l < $ r ) { $ m = ( $ l + $ r ) / 2 ; if ( check ( $ m , $ n ) ) $ r = $ m ; else $ l = $ m + 1 ; } if ( ! check ( $ l , $ n ) ) return floor ( $ l + 1 ) ; else return floor ( $ l ) ; } function countDivisor ( $ n ) { return $ n - bs ( $ n ) + 1 ; } $ n = 5 ; echo countDivisor ( $ n ) ; ? >