Count numbers up to N having exactly 5 divisors

Namachila November 19, 2025

0 0 18 minutes read

Given a positive integer N, the task is to count the number of integers from the range [1, N] having exactly 5 divisors.

Examples:

Input: N = 18
Output: 1
Explanation:
From all the integers over the range [1, 18], 16 is the only integer that has exactly 5 divisors, i.e. 1, 2, 8, 4 and 16.
Therefore, the count of such integers is 1.

Input: N = 100
Output: 2

Naive Approach: The simplest approach to solve the given problem is to iterate over the range [1, N] and count those integers in this range having the count of divisors as 5.

C++

// C++ code for the approach
 
#include <iostream>
#include <cmath>
 
using namespace std;
 
void SieveOfEratosthenes(int n, bool prime[],
                         bool primesquare[], int a[]) {
      
    //For more details check out: https://www.zambiatek.co.uk/sieve-of-eratosthenes/
      
    // Create a boolean array "prime[0..n]" and
    // initialize all entries it as true. A value
    // in prime[i] will finally be false if i is
    // Not a prime, else true.
    for (int i = 2; i <= n; i++)
        prime[i] = true;
  
    // Create a boolean array "primesquare[0..n*n+1]"
    // and initialize all entries it as false. A value
    // in squareprime[i] will finally be true if i is
    // square of prime, else false.
    for (int i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
  
    // 1 is not a prime number
    prime[1] = false;
  
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
            // Update all multiples of p starting from p * p
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
  
    int j = 0;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            // Storing primes in an array
            a[j] = p;
  
            // Update value in primesquare[p*p],
            // if p is prime.
            primesquare[p * p] = true;
            j++;
        }
    }
}
  
// Function to count divisors
int countDivisors(int n) {
    // If number is 1, then it will have only 1
    // as a factor. So, total factors will be 1.
    if (n == 1)
        return 1;
  
    bool prime[n + 1], primesquare[n * n + 1];
  
    int a[n]; // for storing primes upto n
  
    // Calling SieveOfEratosthenes to store prime
    // factors of n and to store square of prime
    // factors of n
    SieveOfEratosthenes(n, prime, primesquare, a);
  
    // ans will contain total number of distinct
    // divisors
    int ans = 1;
  
    // Loop for counting factors of n
    for (int i = 0;; i++) {
        // a[i] is not less than cube root n
        if (a[i] * a[i] * a[i] > n)
            break;
  
        // Calculating power of a[i] in n.
        int cnt = 1; // cnt is power of prime a[i] in n.
        while (n % a[i] == 0) // if a[i] is a factor of n
        {
            n = n / a[i];
            cnt = cnt + 1; // incrementing power
        }
  
        // Calculating the number of divisors
        // If n = a^p * b^q then total divisors of n
        // are (p+1)*(q+1)
        ans = ans * cnt;
    }
  
    // if a[i] is greater than cube root of n
  
    // First case
    if (prime[n])
        ans = ans * 2;
  
    // Second case
    else if (primesquare[n])
        ans = ans * 3;
  
    // Third case
    else if (n != 1)
        ans = ans * 4;
  
    return ans; // Total divisors
}
 
// Function to count the number of integers with exactly 5 divisors
int countIntegers(int n) {
      // Store count of numbers with exactly 5 divisors
      int count = 0;
   
    // loop from 1 to n to check its distinct count of divisors
      for (int i = 1; i <= n; i++) {
          // Function Call
        int divisors = countDivisors(i);
           
        // If the number of divisors is 5, check if it is a prime square
        if (divisors == 5 ) {
            count++;
        }
    }
   
    return count;
}
 
// Driver code
int main() {
    int n = 100;
    cout << countIntegers(n) << endl;
    return 0;
}

Java

// Java code for the approach
 
import java.util.Vector;
 
public class GFG {
    static void SieveOfEratosthenes(int n, boolean prime[],
                                    boolean primesquare[],
                                    int a[])
    {
        // Create a boolean array "prime[0..n]" and
        // initialize all entries it as true. A value
        // in prime[i] will finally be false if i is
        // Not a prime, else true.
        for (int i = 2; i <= n; i++)
            prime[i] = true;
 
        /* Create a boolean array "primesquare[0..n*n+1]"
         and initialize all entries it as false.
         A value in squareprime[i] will finally
         be true if i is square of prime,
         else false.*/
        for (int i = 0; i < ((n * n) + 1); i++)
            primesquare[i] = false;
 
        // 1 is not a prime number
        prime[1] = false;
 
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * 2; i <= n; i += p)
                    prime[i] = false;
            }
        }
 
        int j = 0;
        for (int p = 2; p <= n; p++) {
            if (prime[p]) {
                // Storing primes in an array
                a[j] = p;
 
                // Update value in
                // primesquare[p*p],
                // if p is prime.
                primesquare[p * p] = true;
                j++;
            }
        }
    }
 
    // Function to count divisors
    static int countDivisors(int n)
    {
        // If number is 1, then it will
        // have only 1 as a factor. So,
        // total factors will be 1.
        if (n == 1)
            return 1;
 
        boolean prime[] = new boolean[n + 1];
        boolean primesquare[] = new boolean[(n * n) + 1];
 
        // for storing primes upto n
        int a[] = new int[n];
 
        // Calling SieveOfEratosthenes to
        // store prime factors of n and to
        // store square of prime factors of n
        SieveOfEratosthenes(n, prime, primesquare, a);
 
        // ans will contain total number
        // of distinct divisors
        int ans = 1;
 
        // Loop for counting factors of n
        for (int i = 0;; i++) {
            // a[i] is not less than cube root n
            if (a[i] * a[i] * a[i] > n)
                break;
 
            // Calculating power of a[i] in n.
            // cnt is power of prime a[i] in n.
            int cnt = 1;
 
            // if a[i] is a factor of n
            while (n % a[i] == 0) {
                n = n / a[i];
 
                // incrementing power
                cnt = cnt + 1;
            }
 
            // Calculating the number of divisors
            // If n = a^p * b^q then total
            // divisors of n are (p+1)*(q+1)
            ans = ans * cnt;
        }
 
        // if a[i] is greater than cube root
        // of n
 
        // First case
        if (prime[n])
            ans = ans * 2;
 
        // Second case
        else if (primesquare[n])
            ans = ans * 3;
 
        // Third case
        else if (n != 1)
            ans = ans * 4;
 
        return ans; // Total divisors
    }
 
    // Function to count the number of integers with exactly
    // 5 divisors
    static int countIntegers(int n)
    {
        // Store count of numbers with exactly 5 divisors
        int count = 0;
 
        // loop from 1 to n to check its distinct count of
        // divisors
        for (int i = 1; i <= n; i++) {
            // Function Call
            int divisors = countDivisors(i);
 
            // If the number of divisors is 5, check if it
            // is a prime square
            if (divisors == 5) {
                count++;
            }
        }
 
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 100;
        System.out.println(countIntegers(N));
    }
}

Python3

# Python3 code for the approach
 
import math
 
def sieveOfEratosthenes(n):
    # Create a boolean array "prime[0..n]" and initialize
    # all entries it as true. A value in prime[i] will
    # finally be false if i is Not a prime, else true.
    prime = [True for i in range(n+1)]
    p = 2
    while(p * p <= n):
        # If prime[p] is not changed, then it is a prime
        if (prime[p] == True):
            # Update all multiples of p
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
  
    # Store prime numbers
    primes = []
    for p in range(2, n+1):
        if prime[p]:
            primes.append(p)
  
    return primes
  
# Function to count divisors
def countDivisors(n, primes):
    # If number is 1, then it will have only 1 as a factor.
    # So, total factors will be 1.
    if (n == 1):
        return 1
  
    ans = 1
  
    # Loop for counting factors of n
    i = 0
    while (primes[i] <= math.sqrt(n)):
        # a[i] is not less than square root of n
        cnt = 1 # cnt is power of prime a[i] in n.
        while (n % primes[i] == 0): # if a[i] is a factor of n
            n = n // primes[i]
            cnt += 1 # incrementing power
        ans = ans * cnt # Calculating the number of divisors
        i += 1
  
    # if a[i] is greater than square root of n
    if (n > 1):
        ans = ans * 2
  
    return ans # Total divisors
  
# Function to count the number of integers with exactly 5 divisors
def countIntegers(n):
    # Store count of numbers with exactly 5 divisors
    count = 0
   
    # Get all prime numbers up to n
    primes = sieveOfEratosthenes(n)
   
    # loop from 1 to n to check its distinct count of divisors
    for i in range(1, n+1):
        # Function Call
        divisors = countDivisors(i, primes)
           
        # If the number of divisors is 5, check if it is a prime square
        if (divisors == 5 and int(math.sqrt(i))**2 == i):
            count += 1
   
    return count
  
# Driver code
if __name__ == "__main__":
  # Input integer
  n = 100
   
  # Function call
  print(countIntegers(n))

Javascript

function sieveOfEratosthenes(n)
{
 
  // Create a boolean array "prime[0..n]" and initialize
  // all entries it as true. A value in prime[i] will
  // finally be false if i is Not a prime, else true.
  let prime = new Array(n+1).fill(true);
  let p = 2;
  while(p * p <= n)
  {
   
    // If prime[p] is not changed, then it is a prime
    if (prime[p] == true)
    {
     
      // Update all multiples of p
      for (let i = p * p; i <= n; i += p) {
        prime[i] = false;
      }
    }
    p += 1;
  }
 
  // Store prime numbers
  let primes = [];
  for (let p = 2; p <= n; p++) {
    if (prime[p] == true) {
      primes.push(p);
    }
  }
 
  return primes;
}
 
// Function to count divisors
function countDivisors(n, primes) 
{
 
  // If number is 1, then it will have only 1 as a factor.
  // So, total factors will be 1.
  if (n == 1) {
    return 1;
  }
 
  let ans = 1;
 
  // Loop for counting factors of n
  let i = 0;
  while (primes[i] <= Math.sqrt(n))
  {
   
    // a[i] is not less than square root of n
    let cnt = 1; // cnt is power of prime a[i] in n.
    while (n % primes[i] == 0) { // if a[i] is a factor of n
      n = n / primes[i];
      cnt += 1; // incrementing power
    }
    ans = ans * cnt; // Calculating the number of divisors
    i += 1;
  }
 
  // if a[i] is greater than square root of n
  if (n > 1) {
    ans = ans * 2;
  }
 
  return ans; // Total divisors
}
 
// Function to count the number of integers with exactly 5 divisors
function countIntegers(n) {
  // Store count of numbers with exactly 5 divisors
  let count = 0;
 
  // Get all prime numbers up to n
  let primes = sieveOfEratosthenes(n);
 
  // loop from 1 to n to check its distinct count of divisors
  for (let i = 1; i <= n; i++)
  {
   
    // Function Call
    let divisors = countDivisors(i, primes);
 
    // If the number of divisors is 5, check if it is a prime square
    if (divisors == 5 && Math.sqrt(i)**2 == i) {
      count += 1;
    }
  }
 
  return count;
}
 
// Driver code
let n = 100;
console.log(countIntegers(n));

Output

Time Complexity: O(N^4/3)
Auxiliary Space: O(1)

Efficient Approach: The above approach can also be optimized by observing a fact that the numbers that have exactly 5 divisors can be expressed in the form of p⁴, where p is a prime number as the count of divisors is exactly 5. Follow the below steps to solve the problem:

Generate all primes such that their fourth power is less than 10¹⁸ by using Sieve of Eratosthenes and store it in vector, say A[].
Initialize two variables, say low as 0 and high as A.size() – 1.
For performing the Binary Search iterate until low is less than high and perform the following steps:
- Find the value of mid as the (low + high)/2.
- Find the value of fourth power of element at indices mid (mid – 1) and store it in a variable, say current and previous respectively.
- If the value of current is N, then print the value of A[mid] as the result.
- If the value of current is greater than N and previous is at most N, then print the value of A[mid] as the result.
- If the value of current is greater than N then update the value of high as (mid – 1). Otherwise, update the value of low as (mid + 1).

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define ll long long int
const int MAX = 1e5;
using namespace std;
 
// Function to calculate the value of
// (x^y) using binary exponentiation
ll power(ll x, unsigned ll y)
{
    // Stores the value of x^y
    ll res = 1;
 
    // Base Case
    if (x == 0)
        return 0;
 
    while (y > 0) {
 
        // If y is odd multiply
        // x with result
        if (y & 1)
            res = (res * x);
 
        // Otherwise, divide y by 2
        y = y >> 1;
 
        x = (x * x);
    }
    return res;
}
 
// Function to perform the Sieve Of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
void SieveOfEratosthenes(
    vector<pair<ll, ll> >& v)
{
    bool prime[MAX + 1];
 
    memset(prime, true, sizeof(prime));
 
    prime[1] = false;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed
        // then it is a prime
        if (prime[p] == true) {
 
            // Set all the multiples of
            // p to non-prime
            for (int i = p * 2;
                 i <= MAX; i += p)
                prime[i] = false;
        }
    }
 
    int num = 1;
 
    // Iterate over the range [1, MAX]
    for (int i = 1; i <= MAX; i++) {
 
        // Store all the prime number
        if (prime[i]) {
            v.push_back({ i, num });
            num++;
        }
    }
}
 
// Function to find the primes having
// only 5 divisors
int countIntegers(ll n)
{
    // Base Case
    if (n < 16) {
        return 0;
    }
 
    // First value of the pair has the
    // prime number and the second value
    // has the count of primes till that
    // prime numbers
    vector<pair<ll, ll> > v;
 
    // Precomputing all the primes
    SieveOfEratosthenes(v);
 
    int low = 0;
    int high = v.size() - 1;
 
    // Perform the Binary search
    while (low <= high) {
 
        int mid = (low + high) / 2;
 
        // Calculate the fourth power of
        // the curr and prev
        ll curr = power(v[mid].first, 4);
        ll prev = power(v[mid - 1].first, 4);
 
        if (curr == n) {
 
            // Return value of mid
            return v[mid].second;
        }
 
        else if (curr > n and prev <= n) {
 
            // Return value of mid-1
            return v[mid - 1].second;
        }
        else if (curr > n) {
 
            // Update the value of high
            high = mid - 1;
        }
 
        else {
 
            // Update the value of low
            low = mid + 1;
        }
    }
    return 0;
}
 
// Driver Code
int main()
{
    ll N = 100;
    cout << countIntegers(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.Vector;
 
public class GFG {
    static int MAX = (int)1e5;
 
    public static class pair {
        long first;
        long second;
        pair(long first, long second)
        {
            this.first = first;
            this.second = second;
        }
    }
    // Function to calculate the value of
    // (x^y) using binary exponentiation
    static long power(long x, long y)
    {
       
        // Stores the value of x^y
        long res = 1;
 
        // Base Case
        if (x == 0)
            return 0;
 
        while (y > 0) 
        {
 
            // If y is odd multiply
            // x with result
            if ((y & 1) == 1)
                res = (res * x);
 
            // Otherwise, divide y by 2
            y = y >> 1;
 
            x = (x * x);
        }
        return res;
    }
 
    // Function to perform the Sieve Of
    // Eratosthenes to find the prime
    // number over the range [1, 10^5]
    static void SieveOfEratosthenes(Vector<pair> v)
    {
        boolean prime[] = new boolean[MAX + 1];
 
        for (int i = 0; i < prime.length; i++) {
            prime[i] = true;
        }
 
        prime[1] = false;
 
        for (int p = 2; p * p <= MAX; p++) {
 
            // If prime[p] is not changed
            // then it is a prime
            if (prime[p] == true) {
 
                // Set all the multiples of
                // p to non-prime
                for (int i = p * 2; i <= MAX; i += p)
                    prime[i] = false;
            }
        }
 
        int num = 1;
 
        // Iterate over the range [1, MAX]
        for (int i = 1; i <= MAX; i++) {
 
            // Store all the prime number
            if (prime[i]) {
                v.add(new pair(i, num));
                num++;
            }
        }
    }
 
    // Function to find the primes having
    // only 5 divisors
    static long countIntegers(long n)
    {
        // Base Case
        if (n < 16) {
            return 0;
        }
 
        // First value of the pair has the
        // prime number and the second value
        // has the count of primes till that
        // prime numbers
        Vector<pair> v = new Vector<>();
 
        // Precomputing all the primes
        SieveOfEratosthenes(v);
 
        int low = 0;
        int high = v.size() - 1;
 
        // Perform the Binary search
        while (low <= high) {
 
            int mid = (low + high) / 2;
 
            // Calculate the fourth power of
            // the curr and prev
            long curr = power(v.get(mid).first, 4);
            long prev = power(v.get(mid - 1).first, 4);
 
            if (curr == n) {
 
                // Return value of mid
                return v.get(mid).second;
            }
 
            else if (curr > n && prev <= n) {
 
                // Return value of mid-1
                return v.get(mid - 1).second;
            }
            else if (curr > n) {
 
                // Update the value of high
                high = mid - 1;
            }
 
            else {
 
                // Update the value of low
                low = mid + 1;
            }
        }
        return 0;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        long N = 100;
        System.out.println(countIntegers(N));
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python program for the above approach
 
# Function to calculate the value of
# (x**y) using binary exponentiation
def power(x, y):
    # Stores the value of x**y
    res = 1
    # Base Case
    if x == 0:
        return 0
 
    while y > 0:
        # If y is  odd multiply
        # x with result
        if y&1:
            res = (res*x)
 
        # otherwise, divide y by 2
        y = y >> 1
        x = (x*x)
    return res
 
 
# Function to perform the Sieve of
# Eratosthenes to find the prime
# number over the range [1, 10^5]
def sieveofeartoshenes(vec):
    prime = []
    for i in range(pow(10, 5)+1):
        prime.append(True)
    prime[1] = False
    p = 2
    while (p * p <= pow(10, 5)):
 
        # If prime[p] is not
        # changed, then it is a prime
        if (prime[p] == True):
 
            # Updating all multiples of
            # to non-prime
            for i in range(p * p, pow(10, 5) + 1, p):
                prime[i] = False
        p += 1
    num = 1
 
    # Iterate over the range [1, pow(10, 5)]
    for i in range(1, pow(10, 5)+1):
        # Stores all the prime number
        if prime[i]:
            vec.append([i, num])
            num += 1
 
def count_integer(n):
    # Base Case
    if n < 16:
        return 0
 
        # First value of the pair has the
        # prime number and the second value
        # has the cont of primes till that
        # prime numbers
 
    vec = [[]]
    # precomputing all the primes
    sieveofeartoshenes(vec)
    low = 0
    high = len(vec)-1
 
    # perform the Binary Search
    while low <= high:
        mid = (low+high)//2
        # Calculate the fourth power of
        # the curr and prev
        curr = power(vec[mid][0], 4)
        prev = power(vec[mid-1][0], 4)
 
        if curr == n:
            # Return value of mid
            return vec[mid][1]
 
        elif curr > n and prev <= n:
            # Return value of mid-1
            return vec[mid-1][1]
        elif curr > n:
            # Update the value of low
            high = mid - 1
 
        else:
            # Update the value of high
            low = mid + 1
 
n = 100
ans = count_integer(n)
print(ans)
 
# This code is contributed by Aditya Sharma

C#

// C# code to implement the approach
 
using System;
using System.Collections.Generic;
 
public class pair {
    public long first;
    public long second;
    public pair(long first, long second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG {
    static int MAX = (int)1e5;
 
    // Function to calculate the value of
    // (x^y) using binary exponentiation
    static long power(long x, long y)
    {
 
        // Stores the value of x^y
        long res = 1;
 
        // Base Case
        if (x == 0)
            return 0;
 
        while (y > 0) {
 
            // If y is odd multiply
            // x with result
            if ((y & 1) == 1)
                res = (res * x);
 
            // Otherwise, divide y by 2
            y = y >> 1;
 
            x = (x * x);
        }
        return res;
    }
 
    // Function to perform the Sieve Of
    // Eratosthenes to find the prime
    // number over the range [1, 10^5]
    static void SieveOfEratosthenes(List<pair> v)
    {
        bool[] prime = new bool[MAX + 1];
 
        for (int i = 0; i < prime.Length; i++) {
            prime[i] = true;
        }
 
        prime[1] = false;
 
        for (int p = 2; p * p <= MAX; p++) {
 
            // If prime[p] is not changed
            // then it is a prime
            if (prime[p] == true) {
 
                // Set all the multiples of
                // p to non-prime
                for (int i = p * 2; i <= MAX; i += p)
                    prime[i] = false;
            }
        }
 
        int num = 1;
 
        // Iterate over the range [1, MAX]
        for (int i = 1; i <= MAX; i++) {
 
            // Store all the prime number
            if (prime[i]) {
                v.Add(new pair(i, num));
                num++;
            }
        }
    }
 
    // Function to find the primes having
    // only 5 divisors
    static long countIntegers(long n)
    {
        // Base Case
        if (n < 16) {
            return 0;
        }
 
        // First value of the pair has the
        // prime number and the second value
        // has the count of primes till that
        // prime numbers
        List<pair> v = new List<pair>();
 
        // Precomputing all the primes
        SieveOfEratosthenes(v);
 
        int low = 0;
        int high = v.Count - 1;
 
        // Perform the Binary search
        while (low <= high) {
 
            int mid = (low + high) / 2;
 
            // Calculate the fourth power of
            // the curr and prev
            long curr = power(v[mid].first, 4);
            long prev = power(v[mid - 1].first, 4);
 
            if (curr == n) {
 
                // Return value of mid
                return v[mid].second;
            }
 
            else if (curr > n && prev <= n) {
 
                // Return value of mid-1
                return v[mid - 1].second;
            }
            else if (curr > n) {
 
                // Update the value of high
                high = mid - 1;
            }
 
            else {
 
                // Update the value of low
                low = mid + 1;
            }
        }
        return 0;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        long N = 100;
        Console.WriteLine(countIntegers(N));
    }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript program for the above approach
 
// Function to calculate the value of
// (x**y) using binary exponentiation
function power(x, y)
{
 
    // Stores the value of x**y
    let res = 1;
     
    // Base Case
    if (x === 0) {
        return 0;
    }
 
    while (y > 0) 
    {
     
        // If y is  odd multiply
        // x with result
        if (y&1) {
            res = (res*x);
        }
 
        // otherwise, divide y by 2
        y = y >> 1;
        x = (x*x);
    }
    return res;
}
 
// Function to perform the Sieve of
// Eratosthenes to find the prime
// number over the range [1, 10^5]
function sieveofeartoshenes(vec) {
    let prime = [];
    for (let i = 0; i <= Math.pow(10, 5)+1; i++) {
        prime.push(true);
    }
    prime[1] = false;
    let p = 2;
    while (p * p <= Math.pow(10, 5)) {
 
        // If prime[p] is not
        // changed, then it is a prime
        if (prime[p] === true) {
 
            // Updating all multiples of
            // to non-prime
            for (let i = p * p; i <= Math.pow(10, 5) + 1; i += p) {
                prime[i] = false;
            }
        }
        p += 1;
    }
    let num = 1;
 
    // Iterate over the range [1, pow(10, 5)]
    for (let i = 1; i <= Math.pow(10, 5)+1; i++) 
    {
     
        // Stores all the prime number
        if (prime[i]) {
            vec.push([i, num]);
            num += 1;
        }
    }
}
 
function count_integer(n) 
{
 
    // Base Case
    if (n < 16) {
        return 0;
    }
 
    // First value of the pair has the
    // prime number and the second value
    // has the cont of primes till that
    // prime numbers
    let vec = [[]];
     
    // precomputing all the primes
    sieveofeartoshenes(vec);
    let low = 0;
    let high = vec.length-1;
 
    // perform the Binary Search
    while (low <= high) 
    {
        let mid = (low+high)//2;
         
        // Calculate the fourth power of
        // the curr and prev
        let curr = power(vec[mid][0], 4);
        let prev = power(vec[mid-1][0], 4);
 
        if (curr === n)
        {
         
            // Return value of mid
            return vec[mid][1];
        } 
        else if (curr > n && prev <= n) 
        {
         
            // Return value of mid-1
            return vec[mid-1][1];
        } 
        else if (curr > n)
        {
         
            // Update the value of low
            high = mid - 1;
        } 
        else
        {
         
        // Update the value of high
            low = mid + 1
        }
    }
}
 
let n = 100
let ans = count_integer(n)
console.log(ans)
 
// This code is contributed by phasing17

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

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 zambiatek!