Given a positive integer N. The task is to find the number of divisors (say d) which gives a quotient (say q) on an integer division (i.e q = N/d) such that the quotient has bits or equal set bits than the divisor. In other words, find the number of the possible values of ‘d’ which will produce ‘q’ on an integer dividing ‘n’ (q = N/d) such that ‘q’ has fewer or equal set bits (at least 1) than ‘d’.
Examples :
Input : N = 5
Output : 4
for d = 1 (set bit = 1),
q = 5/1 = 5 (set bit = 2), count = 0.
for d = 2 (set bit = 1),
q = 5/2 = 2 (set bit = 1), count = 1.
for d = 3 (set bit = 2),
q = 5/3 = 1 (set bit = 1), count = 2.
for d = 4 (set bit = 1),
q = 5/4 = 1 (set bit = 1), count = 3.
for d = 5 (set bit = 2),
q = 5/5 = 1 (set bit = 1), count = 4.
Input : N = 3
Output : 2
Observe, for all d > n, q has 0 set bit so there is no point to go above n.
Also, for n/2 < d <= n, it will return q = 1, which has 1 set bit which will always be less than or equal to d. And, the minimum possible value of d is 1. So, the possible value of d is from 1 to n.
Now, observe by dividing n by d, where 1 <= d <= n, it will give q in sorted order (decreasing).
So, with increasing d we will get decreasing q. So, we get the two sorted sequences, one for increasing d
and the other for decreasing q. Now, observe, initially, the number of set bits of d is greater than q, but after a point, the number of set bits of d is less than or equal to q.
So, our problem is reduced to finding that point i.e. ‘x’ for the value of d, from 1 <= d <= n, such that q has less than or equal set bits to d.
So, the count of possible d such that q has less than or equal set bits of d will be equal to n – x + 1.
Below is the implementation of this approach:
C++
// C++ Program to find number of Divisors // which on integer division produce quotient // having less set bit than divisor#include <bits/stdc++.h>using namespace std;// Return the count of set bit.int bit(int x){ int ans = 0; while (x) { x /= 2; ans++; } return ans;}// check if q and d have same number of set bit.bool check(int d, int x){ if (bit(x / d) <= bit(d)) return true; return false;}// Binary Search to find the point at which// number of set in q is less than or equal to d.int bs(int n){ int l = 1, r = sqrt(n); // while left index is less than right index while (l < r) { // finding the middle. int m = (l + r) / 2; // check if q and d have same number of // set it or not. 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;}// Driven Programint main(){ int n = 5; cout << countDivisor(n) << endl; return 0;} |
Java
// Java Program to find number // of Divisors which on integer // division produce quotient // having less set bit than divisorimport java .io.*;class GFG {// Return the count of set bit.static int bit(int x){ int ans = 0; while (x > 0) { x /= 2; ans++; } return ans;}// check if q and d have // same number of set bit.static boolean check(int d, int x){ if (bit(x / d) <= bit(d)) return true; return false;}// Binary Search to find // the point at which// number of set in q is // less than or equal to d.static int bs(int n){ int l = 1, r = (int)Math.sqrt(n); // while left index is // less than right index while (l < r) { // finding the middle. int m = (l + r) / 2; // check if q and d have // same number of // set it or not. 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;} // Driver Code static public void main (String[] args) { int n = 5; System.out.println(countDivisor(n)); }}// This code is contributed by anuj_67. |
Python3
# Python3 Program to find number# of Divisors which on integer# division produce quotient # having less set bit than divisorimport math# Return the count of set bit.def bit(x) : ans = 0 while (x) : x /= 2 ans = ans + 1 return ans# check if q and d have# same number of set bit.def check(d, x) : if (bit(x /d) <= bit(d)) : return True return False; # Binary Search to find# the point at which# number of set in q is # less than or equal to d.def bs(n) : l = 1 r = int(math.sqrt(n)) # while left index is less # than right index while (l < r) : # finding the middle. m = int((l + r) / 2) # check if q and d have # same number of # set it or not. if (check(m, n)) : r = m else : l = m + 1 if (check(l, n) == False) : return math.floor(l + 1) else : return math.floor(l)def countDivisor(n) : return n - bs(n) + 1# Driver Coden = 5print (countDivisor(n))# This code is contributed by # Manish Shaw (manishshaw1) |
C#
// C# Program to find number of Divisors // which on integer division produce quotient // having less set bit than divisorusing System;class GFG {// Return the count of set bit.static int bit(int x){ int ans = 0; while (x > 0) { x /= 2; ans++; } return ans;}// check if q and d have // same number of set bit.static bool check(int d, int x){ if (bit(x / d) <= bit(d)) return true; return false;}// Binary Search to find // the point at which// number of set in q is // less than or equal to d.static int bs(int n){ int l = 1, r = (int)Math.Sqrt(n); // while left index is // less than right index while (l < r) { // finding the middle. int m = (l + r) / 2; // check if q and d have // same number of // set it or not. 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;} // Driver Code static public void Main () { int n = 5; Console.WriteLine(countDivisor(n)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP Program to find number of Divisors // which on integer division produce quotient // having less set bit than divisor// Return the count of set bit.function bit( $x){ $ans = 0; while ($x) { $x /= 2; $ans++; } return $ans;}// check if q and d have// same number of set bit.function check( $d, $x){ if (bit($x /$d) <= bit($d)) return true; return false;}// Binary Search to find// the point at which// number of set in q is // less than or equal to d.function bs(int $n){ $l = 1; $r = sqrt($n); // while left index is less // than right index while ($l < $r) { // finding the middle. $m = ($l + $r) / 2; // check if q and d have // same number of // set it or not. 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;} // Driver Code $n = 5; echo countDivisor($n) ;// This code is contributed by anuj_67.?> |
Javascript
<script> // Javascript Program to find number of Divisors // which on integer division produce quotient // having less set bit than divisor // Return the count of set bit. function bit(x) { let ans = 0; while (x > 0) { x = parseInt(x / 2, 10); ans++; } return ans; } // check if q and d have // same number of set bit. function check(d, x) { if (bit(parseInt(x / d, 10)) <= bit(d)) return true; return false; } // Binary Search to find // the point at which // number of set in q is // less than or equal to d. function bs(n) { let l = 1, r = Math.sqrt(n); // while left index is // less than right index while (l < r) { // finding the middle. let m = parseInt((l + r) / 2, 10); // check if q and d have // same number of // set it or not. 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));</script> |
Output:
4
Time Complexity: O(logN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
