Co-Prime

Hard
0/120
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
TCS

Problem statement

You have an integer ‘N’. Now let’s define a function ‘f(x)’ equal to the number of integers not more than ‘x+1’ and greater than equal to ‘1’ and are coprime to integer ‘x’.

Let’s say there is a number ‘X’ divided by ‘K’ different prime numbers, and let array ‘P’ of length ‘K’ be the array of prime numbers dividing the number ‘X’.

So ‘g(X)’ is equal to the sum of ∑f(X/Pi) ‘i’ in the range ‘[0, K-1]’ both inclusive.

Construct an array ‘Y’ of length ‘N’ where ‘Y[i]’= ‘g(i+1)’ for ‘i’ in the range ‘[0, N-1]’.

Determine the array ‘Y’.

Example: 
'N' = 3
First calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are co-prime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are co-prime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’  and ‘4’ are co-prime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as no prime number divides 1, so ‘g(1) = 0’.
‘g(2)’ = ‘f(2/2)’ = ‘f(1) = 2’ as ‘2’ is the only prime number that divides ‘2’.
‘g(3) = ‘f(3/3)’ = ‘f(1) = 2’ as ‘3’ is the only prime number that divides ‘3’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains one integer, 'N'.
Output format: 
For each test case, output the array ‘Y’.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5


Time Limit: 1 sec
Sample Input 1 :
2
4
5
Sample Output 1 :
0 2 2 2
0 2 2 2 2
Explanation Of Sample Input 1 :
For test case 1:
First, calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are coprime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are coprime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’  and ‘4’ are coprime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as there is no prime number that divides 1 so ‘g(1)=0’.
‘g(2)’ = ‘f(2/2)’ = ‘f(1)’ = ‘2’ as ‘2’ is the only prime number that divides ‘2’.
‘g(3)’ = ‘f(3/3)’ = ‘f(1)’ = ‘2’ as ‘3’ is the only prime number that divides ‘3’.
‘g(4)’ = ‘f(4/2)’ = ‘f(2)’ = ‘2’  as ‘2’ is the only prime number that divides ‘4’.




For test case 2:
First calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are coprime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are coprime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’  and ‘4’ are coprime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as there is no prime number that divides 1 so ‘g(1)=0’.
‘g(2)’ = ‘f(2/2)’ = ‘f(1)’ = ‘2’ as ‘2’ is the only prime number that divides ‘2’.
‘g(3)’ = ‘f(3/3)’ = ‘f(1)’ = ‘2’ as ‘3’ is the only prime number that divides ‘3’.
‘g(4)’ = ’f(4/2)’ = ‘f(2)’ = ‘2’ as ‘2’ is the only prime number that divides ‘4’.
‘g(5)’ = ‘f(5/5)’ = ‘f(1)’ = ‘2’ as ‘5’ is the only prime number that divides ‘5’.
Sample Input 2 :
2
6 
7
Sample Output 2 :
0 2 2 2 2 5
0 2 2 2 2 5 2
Hint

Stimulate the problem statement.

Approaches (2)
Number Theory + Brute Force

Approach:

 

  • First, we must calculate the ‘f(x)’  for all x in the range ‘[1, N]’, both inclusive.
  • To do so, we can form an array ‘phi’ of length ‘N+1’ where ‘phi[i]’ = ‘f(i)’.
  • We can run a nested loop to calculate the array Phi.
  • For ‘i’ the range ‘[1, N]’ both inclusive
    • ‘phi[i]’ = ‘0’.
    • For every ‘j’ in the range ‘[1,i+1]’
    • Increment ‘phi[i]’ if ‘gcd(j, i)==1’
  • Now we have to make a vector of prime numbers dividing for all integers from 1 to ‘N’.
  • To do this, we can use a similar technique of the Sieve of Eratosthenes to store the divisible prime numbers.
  • Now, if we see ‘2*3*5*7*11*13*17’ = ‘510510’, which is greater than ‘100000’, any number less than or equal to ‘100000’ will have a maximum of ‘6’ different prime numbers.
  • To calculate array ‘Y’, just go to all ‘i’ from 1 to ‘N’ and divide i’s prime number by ‘i’ and add the values from array ‘phi’ as stated in the question.

     

Algorithm:

 

  • Initialize an integer array 'phi[N+1]'.
  • Iterate from 'i' = 1 to 'i' = 'N':
    • ‘phi[i]’ = 0;
    • Iterate from j= ‘1’ to ‘j’=i+1
      • If ‘j’ is coprime to ‘i’ increment ‘phi[i]’
      • if( gcd(i,j)==1)’phi[i]’++
  • Initialize an array of vectors of size ‘N+1’ ‘vector<int>primes[N+1]’ to store all prime numbers divisible by all integers from ‘1’ to ‘N’.
  • Iterate from ‘i’= 2 to i= ‘N’
    • if ‘i’ is prime, then it will have no prime number added to it till now.
    • if( primes[i].size==0)
      • Iterate from j=i to j= ‘N’ with ‘j’ increasing by ‘i’ per iteration
        • Push ‘i’ to ‘primes[j]’ as i is prime and is divisible by ‘j’.
        • ‘primes[j].push(i)’;
  • Initialize an array ‘Y’ of length ‘N’.
  • Iterate ‘i’ from ‘i’ = 0 to ‘i’ = ‘N-1’
    • ‘Y[i]’  stores value of ‘g(i+1)’
    • ‘Y[i]’ = ‘0’
    • Iterate j from j=0 to j=primes[i+1].size()
      • Int ‘z’ = ‘(i+1) / (primes[i+1][j])’
      • ‘Y[i]’ += ‘phi[z]’;

           

  • Return array ‘Y’ as the final output.
Time Complexity

O(N^2 Log(N)), where ‘N' is the given integer.

 

Since we are running a nested loop for calculating array ‘Y’, so the overall time complexity will be O(N^2). Also, computing GCD has a time complexity of O(log N). Hence, the overall time complexity is of the order O(N^2 Log N).

Space Complexity

O(N), where ‘N' is the given integer.

 

We form an array ‘Y’ of length ‘N’, an array ‘phi’ of length ‘N’, and a vector array of maximum length ‘N*6’. So overall space complexity is O(8*N), roughly equal to O(N) only.

Code Solution
(100% EXP penalty)
Co-Prime
Full screen
Console