Euler Totient Function Sum

Hard

0/120

Average time to solve is 60m

Contributed by

6 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Hint 1

Hint 2

Try to use some property of the Euler Totient Function.

Approaches (2)

Approach 1

Approach 2

Brute Force

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 )
1. If i is a divisor of ‘N’ ( N % i == 0 ), store it in the ‘ANS’ vector.
Return the ‘ANS’ vector.

Time Complexity

O(N), where ‘N’ is the given number.

We have to check every number from 1 till ‘N’ to find factors. So the time complexity will be O(N).

Space Complexity

O(1).

Constant extra space is used.

(100% EXP penalty)

Euler Totient Function Sum

Console