Count of divisors having more set bits than quotient on dividing N | Java Program to find number of Divisors which on integer division produce quotient having less set bit than divisor ; 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
import java . io . * ; class GFG { static int bit ( int x ) { int ans = 0 ; while ( x > 0 ) { x /= 2 ; ans ++ ; } return ans ; } static boolean check ( int d , int x ) { if ( bit ( x / d ) <= bit ( d ) ) return true ; return false ; } static int bs ( int n ) { int l = 1 , r = ( int ) Math . sqrt ( n ) ; while ( l < r ) { int m = ( l + r ) / 2 ; if ( check ( m , n ) ) r = m ; else l = m + 1 ; } if ( ! check ( l , n ) ) return l + 1 ; else return l ; } static int countDivisor ( int n ) { return n - bs ( n ) + 1 ; } static public void main ( String [ ] args ) { int n = 5 ; System . out . println ( countDivisor ( n ) ) ; } }