Last Updated: 24 Jun, 2021
Euler Totient Function Sum
Hard
Asked in companies
You are given a positive integer ‘N’, your task is to return an array/list of integers such that the sum of Euler Totient Function values of each integer of the array is equal to ‘N’.
Euler Totient Function:
In number theory, Euler's totient function counts the positive integers up to a given integer ‘N’ that is relatively prime to ‘N’.
More details about Euler’s Totient Function can be found here
For Example:
For ‘N’ = 10, if we take the array as 1, 2, 5, 10,
The Euler totient function value of 1 is 1.
The Euler totient function value of 2 is 1.
The Euler totient function value of 5 is 4.
The Euler totient function value of 10 is 4.
So, the summation will be 1 + 1 + 4 + 4 = 10.
Hence this is a valid array for ‘N’ = 10.
Note:
The solution will be verified by the actual value of the Euler Totient Function of 'N' and the sum of the Euler Totient Function of all the values returned. In the output, only the 'YES' or 'NO' is printed, according to the correctness of the solution.
Input Format:
The first line contains a single integer ‘T’, representing the number of test cases.
The first line of each test case contains a single integer ‘N’, representing the sum of the Euler Totient Function values of all the elements of the output array.
Output Format:
For each test case, Return all the elements of the array satisfying the condition given in the problem statement.
If there are multiple answers possible print any one of them.
Output for each test case will be printed in a separate line.
Note
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^3
Time Limit: 1 sec.
Approaches
We will use the divisor sum property of the Euler Totient Function to solve the problem. This property states that any positive integer ‘N’ can be represented as the summation of the Euler Totient Function values of all the divisors of ‘N’.
So, now our task is to only find all the divisors of ‘N’. We can do it by iterating over 1 to ‘N’ and storing all the numbers which divide ‘N’.
Algorithm:
- Initialize a vector ‘ANS’ to store the divisors.
- Start iterating from 1 to ‘N’(say iterator i )
- If i is a divisor of ‘N’ ( N % i == 0 ), store it in the ‘ANS’ vector.
- Return the ‘ANS’ vector.
The approach is similar to the previous one. We will just try to optimize the process of finding all the divisors of ‘N’.
We can observe that the divisors of any integer come in pairs. For each divisor ‘D1’ such that 1 <= ‘D1’ <= sqrt(‘N’) , there will be another divisor ‘D2’ = ‘N’ / ‘D1’ such that sqrt(‘N’) <= ‘D2’ <= ‘N’. But we have to be careful when ‘D1’ is equal to ‘D2’. In that case, we will consider ‘D1’ only once.
We will iterate from 1 to sqrt(‘N’). For each divisor of ‘N’, we will also consider the other divisor ‘N’ / ‘i’ and will count the even and odd divisors accordingly.
Algorithm
- Initialize a vector ‘ANS’ to store the divisors.
- Start iterating from 1 to sqrt(‘N’).
- If the current iterator ( say ‘i’ ) is a divisor of ‘N’ ( ‘N’ % ‘i’ == 0 ):
- If i is not equal to sqrt(‘N’), push both ‘i’ and ‘N’ / ‘i’ to the ‘ANS’ vector.
- Else only push ‘i’ to the ‘ANS’ vector.
- Return the ‘ANS’ vector.