Super Primes Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/super-primes2443/1
(It is also the problem of the day for 02-05-2022)
Solution:
class Solution {
public boolean isPrime(int n){
if(n==2 || n==3){
return true;
}
else if(n==1){
return false;
}
else if((n%2)==0 || (n%3)==0){
return false;
}
else{
for(int i=5;i<Math.sqrt(n)+1;i+=6){
if((n%i)==0 || (n%(i+2))==0){
return false;
}
}
return true;
}
}
int superPrimes(int n) {
HashSet<Integer>set=new HashSet<Integer>();
set.add(2);
set.add(3);
int count=0;
for(int i=5;i<n+1;i++){
if(isPrime(i)==true){
//System.out.println("true");
if(set.contains(i-2)==true){
count++;
}
set.add(i);
}
}
//System.out.println(set);
return count;
}
}
Time Complexity: O(N*Sqrt(N)*1)[GFG Time:0.33/1.18]
[Here O(N) is basically for traversing the array, Sqrt(N) for the checking of prime number or not and O(1) in HashSet contains method. HashSet contains method is not O(logN) as it occurs when the collision happens, while in our code probability of collision is very less due to which time taken will be O(1) only.]
Space Complexity: O(1)
Auxiliary Space: O(N)[HashSet is used]
Total Test Cases:210
Approach Used:
Here we do two things.
1. check if a number is prime or not
2. If the number is prime then whether it is the sum of 2 prime numbers or not.
For checking whether the number is prime or not we use the isPrime() function
After that, if the number is prime then
we will see whether (number-2) is contained in the set or not.
If yes increment count
else add the element in the set
Why we are checking with (number-2)?
It is so because every prime number will be expressed as the sum of 2+other prime numbers.
Without the presence of 2, it won't be cast into super-prime.
ex 5 -> 2+3
7 -> 2+5
11->2+9 but 11 will be not super-prime as 9 is composite.
If number 2 is not present in the set then why we are adding it into the set?
If we don't add the prime number to the set we will miss some results.
eg 1 to 20
traversal starts from 5
number=5 prime = yes set={2,3} set.contains(5-2)==3 yes count=1 set={2,3,5}
number =7 prime=yes set={2,3,5} set.contains(7-2)==5 yes count=2 set={2,3,5,7}
number =11 prime =yes set={2,3,5,7} set.contains(11-2)=9 false count=2 set={2,3,5,7,11}
number =13 prime =yes set={2,3,5,7,11} set.contains(13-2)=11 true count=3 set={2,3,5,7,11,13}
number =17 prime =yes set={2,3,5,7,11,13} set.contains(17-2)=15 false count=2 set={2,3,5,7,11,17}
number =19 prime =yes set={2,3,5,7,11,13,19} set.contains(19-2)=17 true count=4 set={2,3,5,7,11,13,17,19}
Hence our count will be 4 but the set will contain all prime numbers till the range given as 20.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Another approach:
class Solution {
public boolean isPrime(int n){
if(n==2 || n==3){
return true;
}
else if(n==1){
return false;
}
else if((n%2)==0 || (n%3)==0){
return false;
}
else{
for(int i=5;i<Math.sqrt(n)+1;i+=6){
if((n%i)==0 || (n%(i+2))==0){
return false;
}
}
return true;
}
}
int superPrimes(int n) {
ArrayList<Integer>aa=new ArrayList<Integer>();
for(int i=2;i<n;i++){
if(isPrime(i)==true){
aa.add(i);
}
}
// System.out.println(aa);
int count=0;
for(int i=0;i<aa.size();i++){
for(int j=i+1;j<aa.size();j++){
if((aa.get(i)+aa.get(j))%2!=0){
if(isPrime(aa.get(i)+aa.get(j))==true){
//count++;
if((aa.get(i)+aa.get(j))<=n){
count++;
}
}
}
}
}
return count;
}
}
""""""""""""But it will show time limit excedded."""""""""""""""""""""""""""""""""""""""
Time Complexity:O(N*log(N) + N^2)=O(N^2)
Space Complexity: O(1)
Auxiliary Space: O(N)[ArrayList is used]
Total Test Cases:205/210 passed.
Approach :
Checking of all elements in range whether they are prime or not.
If prime add them to the ArrayList.
traverse the ArrayList and using two loops (nested)check the weather:
if the sum of first elemet+ second element is not even and the sum is prime
count++;
return count
Here the first element means one element will be fixed and keeping that element fixed we will traverse all the other elements and take the sum of those elements with the fixed element.
After traversing the whole array we will move the pointer to the next index and make that element fixed.
In such a manner, we will cover up all the elements and hence the time complexity will be O(n^2) due to which it will show Time Limit Exceeded.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment