Count of divisors having more set bits than quotient on dividing N | C ++ 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 . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int bit ( int x ) { int ans = 0 ; while ( x ) { x /= 2 ; ans ++ ; } return ans ; } bool check ( int d , int x ) { if ( bit ( x / d ) <= bit ( d ) ) return true ; return false ; } int bs ( int n ) { int l = 1 , r = 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 ; } int countDivisor ( int n ) { return n - bs ( n ) + 1 ; } int main ( ) { int n = 5 ; cout << countDivisor ( n ) << endl ; return 0 ; }