Count of divisors having more set bits than quotient on dividing N️‍🔥

Q: What is Count of divisors having more set bits than quotient on dividing N?

In this article, we will learn Count of divisors having more set bits than quotient on dividing N,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

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 Program
int 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 divisor
import 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 divisor
import 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 Code
n = 5
print (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 divisor
using 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:

Time Complexity: O(logN)

Auxiliary Space: O(1)