You have given a list of q queries and for every query, you are given an integer N. The task is to find how many numbers less than or equal to N have numbers of divisors exactly equal to 3. Example 1: Input: q = 1 query[0] = 6 Output: 1 Explanation: There is only one number 4 which has exactly three divisors 1, 2 and 4 and less than equal to 6. Example 2: Input: q = 2 query[0] = 6 query[1] = 10 Output: 1 2 Explanation: For query 1 it is covered in the example 1. query 2: There are two numbers 4 and 9 having exactly 3 divisors and less than equal to 10. Your Task: You don't need to read input or print anything. Your task is to complete the function threeDivisors() which takes an integer q and a list of integer of size q as input parameter and returns the list containing the count of the numbers having exactly 3 divisors for each query. Expected Time Complexity: O(NlogN), Expected Auxiliary Space: O(N), where N is min(10^6,N) Constraints : 1 <= q <= 103 1 <= query[i] <= 1012 // { Driver Code Starts //Initial Template for Java import java.io.*; import java.util.*; class GFG { public static void main(String args[])throws IOException { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0){ int q = sc.nextInt(); ArrayList query = new ArrayList<>(); for(int i=0;i ans = ob.threeDivisors(query,q); for(int cnt : ans) { System.out.println(cnt); } } } } // } Driver Code Ends //User function Template for Java class Solution{ static ArrayList threeDivisors(ArrayList query, int q){ // code here } }
You have given a list of q queries and for every query, you are given an integer N. The task is to find how many numbers less than or equal to N have numbers of divisors exactly equal to 3.
Example 1:
Input: q = 1 query[0] = 6 Output: 1 Explanation: There is only one number 4 which has exactly three divisors 1, 2 and 4 and less than equal to 6.
Example 2:
Input: q = 2 query[0] = 6 query[1] = 10 Output: 1 2 Explanation: For query 1 it is covered in the example 1. query 2: There are two numbers 4 and 9 having exactly 3 divisors and less than equal to 10.
Your Task:
You don't need to read input or print anything. Your task is to complete the function threeDivisors() which takes an integer q and a list of integer of size q as input parameter and returns the list containing the count of the numbers having exactly 3 divisors for each query.
Expected Time Complexity: O(NlogN),
Expected Auxiliary Space: O(N), where N is min(10^6,N)
Constraints :
1 <= q <= 103
1 <= query[i] <= 1012
// { Driver Code Starts
//Initial Template for Java
import java.io.*;
import java.util.*;
class GFG
{
public static void main(String args[])throws IOException
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int q = sc.nextInt();
ArrayList<Long> query = new ArrayList<>();
for(int i=0;i<q;i++){
query.add(sc.nextLong());
}
Solution ob = new Solution();
ArrayList<Integer> ans = ob.threeDivisors(query,q);
for(int cnt : ans) {
System.out.println(cnt);
}
}
}
}
// } Driver Code Ends
//User function Template for Java
class Solution{
static ArrayList<Integer> threeDivisors(ArrayList<Long> query, int q){
// code here
}
}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
