Count integers up to N that are equal to at least 2nd power of any integer exceeding 1

Count integers up to N that are equal to at least 2nd power of any integer exceeding 1

Given a positive integer N, the task is to count the number of integers from the range [1, N], that can be represented as a^b, where a and b are integers greater than 1.
Examples:

Input: N = 6
Output: 1
Explanation:
Only such integer from the range [1, 6] is 4 (= 2²).
Therefore, the required count is 1.

Input: N = 10
Output: 3

Approach: The given problem can be solved by counting all the possible pairs of elements (a, b) such that a^b is at most N. Follow the steps below to solve the problem:

• Initialize a HashSet to store all possible values of a^b which is at most N.
• Iterate over the range [2, √N], and for each value of a, insert all possible values of a^b having value at most N, where b lies over the range [1, N].
• After completing the above steps, print the size of the HashSet as the resultant count of integers.

Below is the implementation of the above approach:

Java

import java.util.HashSet;    public class GFG {                       static void printNumberOfPairs(int N)     {                  HashSet<Integer> st             = new HashSet<Integer>();                              for (int i = 2; i * i <= N; i++) {                int x = i;                                          while (x <= N) {                                     x *= i;                                                                       if (x <= N) {                     st.add(x);                 }             }         }                     System.out.println(st.size());     }             public static void main(String args[])     {         int N = 10000;         printNumberOfPairs(N);     } }

Output:

124

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets