Modified Numbers And Queries

Problem Link:

https://practice.geeksforgeeks.org/problems/modified-numbers-and-queries0904/1

Solution:

class Solution

{

    

    public 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 sumOfAll(int l, int r)

    {

        ArrayList<Integer>aa=new ArrayList<Integer>();

        int sum=0;

        for(int i=2;i<l;i++){

            if(isPrime(i)){

                aa.add(i);

            }

        }

        

        for(int i=l;i<=r;i++){

            if(i==1){

                sum=sum+1;

            }

            else{

                if(isPrime(i)){

                    aa.add(i);

                    sum=sum+i;

                }

                else{

                    for(int j=0;j<aa.size();j++){

                        if(i%aa.get(j)==0){

                            sum=sum+aa.get(j);

                        }

                    }

                }

            }

        }

        return sum;

        

    }

    

}

Time Complexity: O(NSQRT(N)Log(Number of Primes))[GFG Time:0.35]

Space Complexity:O(Log(N))

Total Test Cases:10114

Auxiliary Space: O(number of primes)

1. Here we need to find out the sum of all prime numbers which are factors of all the numbers coming during range while traversing from l to r.

Means if l=1 r=9

let us take sum=0

then while traversing with i from(int i=l;i<=r;i++)

i=1 is not prime but for 1 we need to add in sum, so sum=0+1=1

i=2 prime sum=1+2=3

i=3 prime sum=3+3=6

i=4 is not prime so the prime factor is only 2 so sum=6+2=8

i=5 prime sum=8+5=13

i=6 is not prime so prime factors of 6 are 2 and 3 so sum=2+3+13=18

i=7 prime so sum=18+7=25

i=8 is not prime so the prime factor is 2 only so sum=25+2=27

i=9 is not prime so the prime factor is 3 only so sum=27+3=30

return 30

So from the above example only we get to know about the idea:

1. if the number is even then add it to the sum

2. if the number is prime then add it to the sum

3. if the number is not prime then find out the prime numbers till that non-prime number and add their sum to the final sum.

Step 1 is easy and directly we will add 1 to the sum

for Step2 we will apply the separate logic for prime number checking which is written in the isPrime() function

For step3 we need to understand that we have two ways

First Way:

1. directly traversing from 2 to that number.

For example, let number=6 which is not prime so you will apply the loop as

int val=0;

 for(int i=2;i<6;i++){

    if(isPrime(i) && (num%i)==0){

            val=val+i;

    }

  }    

sum=sum+val;

In such case, we will every time iterate to that number from 2 to find out the prime numbers in that range which are divisors too, and add them to the final sum.

So in the worst case, we can say that for the very large numbers we ultimately need to check for prime numbers and divisors also so it will mount to O(N)

here n means the extreme value in the range for l=1 to r=10 extreme value will be 10

so one loop for l to r and one loop from 2 to l when l=10

ultimately nearly O(N^2) will be the complexity of the following code.

Second Way:

While traversing we will store the prime number in a separate ArrayList.

Question What will be the benefit of it and moreover it will take separate space?

Answer:

As per our question, we don't have any problem with prime numbers 

but for non-prime numbers, we need their factors, as well as those factors, should be prime

So ultimately if we think off logically we need prime factors and prime factors throughout the traversal will be the same as 

For example till 6 we will get 2,3, and 5 as primes

similarly, till 12 we will get 2, 3, 5, 7, and 11 as primes

So if we observe clearly we are getting 2, 3, and 5 in both cases so why check for them every time as l values increases in the loop which will ultimately 

1. increase time complexity of code

2. every time checking for the same value to be prime or not by calling the isPrime() function

So in a manner, we come up with storage of prime numbers in the ArrayList.

And hence we store the prime numbers in ArrayList we are left with only one condition of checking whether those prime numbers will be a factor of number also or not. 

So we create an ArrayList which will store all the primes and once we reach a nonprime number we will traverse that ArrayList and see whether it contains any element that is a factor of a given number or not. 

If yes then we will add them to the sum variable 

else we will continue our traversal.

In such a way, we will get the final sum and return it.

Question: In question expected time complexity is O(nloglogn) but you are taking O(sqrt(n)log(number of primes)) which is somewhat more than actual than how it is running?

Answer: Actually the increment is time complexity is due to 

1. logic of prime number checking function which is taking O(sqrtn) time as in it loop will go to sqrt(n)

The code is working because.:

In the given question expected time is O(n) but here we will be having very less time, as our ArrayList will only store prime factors and which is not even O(LogN) so it will be very less.

So this is what we call Time-Memory Trade-Off.

Our code cuts its time in memory to overcome its excess time in Time complexity.

"Thanks For Reading.😊"

"Share Further To Increase Knowledge Treasure.😇"