Return Two Prime Numbers Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/return-two-prime-numbers2509/1#
It is also the problem of the day for 24-02-2022
Solution:
class Solution{
public static boolean isPrime(int n){
if(n==1){
return false;
}
if(n==2 || n==3){
return true;
}
else if(n%2==0 || n%3==0){
return false;
}
else{
boolean flag=true;
for(int i=5;i<=Math.sqrt(n);i+=6){
if((n%i)==0 || n%(i+2)==0){
flag=false;
break;
}
}
if(flag==false){
return false;
}
else{
return true;
}
}
}
static List<Integer> primeDivision(int n){
ArrayList<Integer>aa=new ArrayList<Integer>();
for(int i=1;i<(n);i++){
if(isPrime(i)==true){
aa.add(i);
}
}
//System.out.println(aa);
int start=0;
int end=aa.size()-1;
int a=aa.get(start)+aa.get(end);
while(a!=n){
if(a>n){
end--;
a=aa.get(start)+aa.get(end);
}
else if(a<n){
start++;
a=aa.get(start)+aa.get(end);
}
}
ArrayList<Integer>ab=new ArrayList<Integer>();
ab.add(aa.get(start));
ab.add(aa.get(end));
return ab;
}
}
Time Complexity:
O(N*Sqrt(N))[For first loop]+O(N)[For second loop]=O(N*Sqrt(N))
[In the first loop,
we start traversing ie O(N) and check for every number ie O(Sqrt(N)). So overall=O(N*Sqrt(N))
In the second loop,
We are using two pointer approach and in the worst case, it will be when either start or end one remains fixed, and the other traverses the whole array.
if the start is fixed then the end comes from the last index(n-1) to the second index(1).
if the end is fixed then the start goes from 0 to n-2(second last index).
]
GFG Time:0.2/11.1
Space Complexity: O(1)
Auxiliary Space: O(N)[Arraylists are used]
Approach Used:
Here, first of all, we will store all prie number up to the given number and then using two pointer approach we will find out the sum of pair and as said in question there will be at least one pair so the first pair we got we will store the values at those indexes as a start will be minimum and end will be maximum (as desired in question).
For prime number storage, we traverse the whole array and check for each value if it is prime then store it in ArrayList aa.
Later we will traverse the ArrayList aa using two pointer approach and find out the value of start and end when aa. get(start)+aa.get(end)=n.
Once we got the start and end values we will store the corresponding ArrayList values in another list and return the new list.
Total Test Cases:75
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment