3 Divisors Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/3-divisors3942/1
It is also the problem of the day for 8-12-2022
Solution:
//{ 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<Long>aa=new ArrayList<Long>();
//for checking prime
public static boolean isPrime(int a){
if(a==1){
return false;
}
else if(a==2 || a==3){
return true;
}
else if(a%2==0 || a%3==0){
return false;
}
else{
for(int i=5;i<=Math.sqrt(a);i+=6){
if(a%i==0 || a%(i+2)==0){
return false;
}
}
return true;
}
}
//for checking whether a number is a perfect square or not
public static boolean fun2(long n){
double a=Math.sqrt(n);
double b=Math.floor(a);
if((a-b)==0)
{
int a1=(int)a;
if(isPrime(a1)){
return true;
}
return false;
}
return false;
}
//for traversing till n value
public static int fun1(long n){
int count=0;
for(int i=4;i<=n;i++){
if(fun2(i)==true){
count++;
}
}
return count;
}
//main function
static ArrayList<Integer> threeDivisors(ArrayList<Long> query, int q){
ArrayList<Integer>ab=new ArrayList<Integer>();
for(int i=0;i<q;i++){
long a=query.get(i);
ab.add(fun1(a));
}
return ab;
}
}
Time Complexity:O(Q*N*LOG(N))
Space Complexity: O(Q)[ArrayList is used for storing counters.]
Auxiliary Space:O(Q)[ArrayList is used]
Total Test Cases:91
Total Time Taken:0.58
Approach Used:
Here we need to observe one thing for any number to have exactly 3 divisors there should exist 1,p, and p*2. where p is the square root of the number.
So for example, if the number is 24 then the divisors are 1,2,3,4,6,12,24 not exactly 3
for number 3 divisors will be 1 and 3 only not exactly 3
for number 76 divisors will be 1,2,4,19,38,76 not exactly 3
similarly for number 343 divisors will be 1,7,49,343
while for number 25 divisors will be 1,5,25 exactly 3
and for 121 it will be 1,11,121 exactly 3
So if observe one thing, we need to do 2 things
1. Check whether the number is a perfect square or not.
If not then we can see the case of 76 and 24 which have more than 3 divisors and similarly for 3 which has less than 3 divisors.
2. Check whether the number selected has divisors that are prime or not.
If not then we can observe the case of 343 where divisors are not prime ie 49 and hence for 343 there are more than 3 divisors.
For having exactly 3 divisors: the first divisor will be 1, the second will be the square root of that number(p=sqrt(number)), and the third will be that number itself(p*2). So ultimately we will need to check whether the square root of that number is prime or not.
So we have to follow some steps:
1. Traverse till q and for each value check the above two conditions.
2. For every value passed we need to traverse from 4 to that number and check whether that number is a perfect square or not.
If not then we will not increment the counter, while if it is a perfect square then we will also check whether the square root of that number is prime or not.
If that number is prime we will increase the counter hence no change in the value of count.
3. Simultaneously for every value we will add the count value till that number in ArrayList ab
4. return ab.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment