Last Updated: 23 Oct, 2021
Ninja and Positive Integers
Easy
Asked in company
Ninja likes to play with positive integers. One day he found a positive integer ‘N’ and started to think about 3 positive integers which will sum up to ‘N’ but the LCM of these integers should be less than or equal to ‘N’/2, i.e.,
a1 + a2 + a3 = N
LCM(a1, a2, a3) <= N/2
Since this task is too simple for Ninja, he asked you to find the three numbers satisfying the above conditions.
For Example:
Let N = 4, then we can choose 1, 1, and 2. The sum of these integers is 4 which is equal to ‘N’ and their LCM is 2 which is <= N/2.
Input Format:
The first line will contain a single integer ‘T’ denoting the number of test cases. Then the test cases follow.
The first line of each test case will contain a single integer ‘N’, denoting the positive integer Ninja has.
Output Format:
For each test case, print three space-separated integers satisfying the required conditions.
You can print the integers in any order.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 1000
3 <= N <= 10^9
Time Limit: 1 sec.
Approaches
We will iterate over all the possible values for each integer and the combination of integers that satisfies the required conditions will be the answer.
Algorithm:
- Declare a vector of integers “ans” to store the answer.
- Iterate from 1 to ‘N’ for the first integer ‘i’.
- Iterate from 1 to ‘N’ for the second integer ‘j’.
- Iterate from 1 to ‘N’ for the third integer ‘k’.
- Calculate the LCM of ‘i’, ‘j’, and ‘k’ and store them in ‘L’.
- If the sum of the integers is equal to ‘N’ and ‘L’ is less than or equal to ‘N’/2.
- Push ‘i’, ‘j’, and ‘k’ to the “ans” and return it.
- Iterate from 1 to ‘N’ for the third integer ‘k’.
- Iterate from 1 to ‘N’ for the second integer ‘j’.
Observe that if ‘N’ is odd, then the answer will be ‘N’/2, ‘N’/2, and 1. Because since ‘N’ is odd (‘N’/2 + ‘N’/2) will equal to (‘N’ - 1) and hence we can get an extra 1 to add which will be our third integer. And the LCM of them will also be ‘N’/2 which satisfies our condition.
Otherwise, if ‘N’ is divisible by 4, then the answer will be ‘N’/2, ‘N’/4, and ‘N’/4. Here (‘N’/2 + ‘N’/4 + ‘N’/4) will sum up to ‘N’ and their LCM will be ‘N’/2 since ‘N’/4 are factors of ‘N’/2.
Else, if ‘N’ is even by not divisible by 4, then the answer will be ‘N’/2 - 1, ‘N’/2 - 1, 2. Because here (‘N’/2 - 1 + ‘N’/2 - 1) will equal to (‘N’ - 2) and hence we got 2 as our third integer. Moreover, since ‘N’ is even but ‘N’ is not divisible by 4, ‘N’/2 will be odd and as a result (‘N’/2 - 1) will be even. Again 2 is a factor of every even number. So the LCM of these integers will be (‘N’/2 - 1) which is less than ‘N’/2.
Algorithm:
- Declare a vector of integers “ans” to store the answer.
- If ‘N’ is odd.
- Push ‘N’/2, ‘N’/2, and 1 to the “ans”.
- Else if ‘N’ is divisible by 4.
- Push ‘N’/2, ‘N’/4, and ‘N’/4 to the “ans”.
- Else.
- Push ‘N’/2 - 1, ‘N’/2 - 1, 2 to the “ans”.
- Finally, return the “ans”.