Count of divisors having more set bits than quotient on dividing N | Python3 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 math NEW_LINE def bit ( x ) : NEW_LINE INDENT ans = 0 NEW_LINE while ( x ) : NEW_LINE INDENT x /= 2 NEW_LINE ans = ans + 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT def check ( d , x ) : NEW_LINE INDENT if ( bit ( x / d ) <= bit ( d ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False ; NEW_LINE DEDENT def bs ( n ) : NEW_LINE INDENT l = 1 NEW_LINE r = int ( math . sqrt ( n ) ) NEW_LINE while ( l < r ) : NEW_LINE INDENT m = int ( ( l + r ) / 2 ) NEW_LINE if ( check ( m , n ) ) : NEW_LINE INDENT r = m NEW_LINE DEDENT else : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT DEDENT if ( check ( l , n ) == False ) : NEW_LINE INDENT return math . floor ( l + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return math . floor ( l ) NEW_LINE DEDENT DEDENT def countDivisor ( n ) : NEW_LINE INDENT return n - bs ( n ) + 1 NEW_LINE DEDENT n = 5 NEW_LINE print ( countDivisor ( n ) ) NEW_LINE