Help Ishaan

Problem Link:

https://practice.geeksforgeeks.org/problems/help-ishaan5837/1

(It is also the problem of the day for 09-10-2022)

JAVA:

------------------------------------------------------------------------------------------------------------>

Solution:

class Solution
{
    public static boolean isPrime(int n){
        if(n==1){
            return false;
        }
        else if(n==2 || n==3){
            return true;
        }
        else if(n%2==0 || n%3==0){
            return false;
        }
        else{
            for(int i=5;i<=Math.sqrt(n);i+=6){
                if(n%(i)==0 || n%(i+2)==0){
                    return false;
                }
            }
            return true;
        }
        
    }
    public int NthTerm(int n)
    {
        if(isPrime(n)==true){
            return 0;
        }
        else{
          
            int diff=0;
            if(n-19<=0){
                diff=0;
            }
            else{
                diff=n-19;
            }
            int min=Integer.MAX_VALUE;
            for(int i=diff;i<(n+19);i++){
                if(isPrime(i)){
                    min=Integer.min((int)Math.abs(i-n),min);
                }
            }
            return min;
            
          
        }
    }
}

Time Complexity:O(Sqrt(n)(n+-19))[Total time taken:0.21]

Space Complexity:O(1)

Auxiliary Space:O(1)

Approach Used:

1. Here we need to find out the difference between the closest prime number with respect to the given number.

2. If the number given is prime then the difference will be 0.

3. If the number is not prime then we need to find out the closest prime number to it and that prime number can either be on the left side or right side.

4. So what we need to do is we need to take up a range from left to right and find out the prime number.

5. Here we have taken the range from n-19 to n+19 and then calculated the difference between numbers in the range and the given number and print out the min difference value.

Question?

Why you have taken the range from n-19 to n+19?

Solution:

1. I thought of finding out the minimum difference between two prime numbers.

2. It means that if we have one prime number then we want to observe how many values
we will get the prime numbers either on the left side or right side.

For example:

for small integer values like 5, we get the prime number as 7 on its right side and 3 on its left side with a difference of 2.

So in such a manner, if we get the minimum difference between two prime numbers then definitely in that range only we will get the correct answer.

For small numbers like 11 13 if we observe clearly then in every row from 10 to 20 or 20 to 30 we get some prime numbers so we can say that from n-10 to n+10 we will get some prime numbers and the number with which we will have minimum difference we will return that difference.

However certainly for every number this range does not satisfy as when we will have large numbers it might get fail.

3. So taking that into mind I started with different ranges and then test up the code:

n-100 to n+100 passed

n-50 to n+50 passed

n-30 to n+30 passed

n-20 to n+20 passed

n-15 to n+15 failed

n-17 to n+17 failed

n-19 to n+19 passed

5. So it showed me that the minimum difference between prime numbers less 100000 is 19 and it can be either on the right side or left side.

6. And due to this our traversal time restricts to taking constant time and hence time complexity of our code is only left to check whether the number is prime or not and which is sqrt(n) only.

Moreover, we did not use any extra space of Auxiliary space is also O(1)

Total Test Cases:10200

================================================================

C++:

public:
	bool isPrime(int x)

 {

     for(int i=2;i<=sqrt(x);i++)

     {

         if(x%i==0)return false;

     }

     return true;

 }

 int NthTerm(int N){

     // Code here
     if(N==1){
         return 1;
     }

     int t,k;

     for(int i=N;i>=2;i--)

     {

         if(isPrime(i))

         {

             t=i;

             break;

         }

     }

     for(int i=N+1;i<2*N;i++)

     {

         if(isPrime(i))

         {

             k=i;

             break;

         }

     }

     return min(abs(t-N),abs(k-N));
 }

};

Approach Used:
1.Starting from num to 2 in first loop and as find the prime number break the loop.
2.Starting from num+1 to 2*num and as the prime number comes break the second loop.
3.Find out the min between two differces of two values taken from loop with respec to number given.

Time Complexity:O((N/2)*Sqrt(n))[Total time taken:0.04]
Space Complexity:O(1)
Auxiliary Space:O(1)
On left side you will go from n to n/2 and on right side you will go from n to 2*n.

Note:
C++ is faster than Java So time complexity differs in such a way.

--------------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😀"

.......................................................................................................................................