Problem

Submissions

Hints & solutions

Discuss

Ninja and Positive Integers

Easy

0/40

Average time to solve is 20m

Contributed by

0 upvote

Asked in company

Problem statement

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.

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

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.

Sample Input 1:

2
3
6

Sample Output 1:

1 1 1
2 2 2

Explanation For Sample Output 1:

For the first test case, we can choose 1, 1, and 1. Their sum is 3 and LCM is 1.

For the second test case, we can choose 2,2, and 2. Their sum is 6 and LCM is 2.

Sample Input 2:

2
10
7

Sample Output 2:

4 4 2
1 3 3

Hint 1

Hint 2

Try to consider all the possible values for each integer and find the combination which satisfies the conditions.

Approaches (2)

Approach 1

Approach 2

Brute-Force

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.

Time Complexity

O(N ^ 3), where ‘N’ is the integer Ninja has.

Since we are iterating over ‘N’ for all the three integers, the overall time complexity will be O(N ^ 3).

Space Complexity

O(1).

Constant space is used.

(100% EXP penalty)

Ninja and Positive Integers

Console