Выведите триплет с суммой, равной N, и LCM не более N/2.
Для данного положительного целого числа N задача состоит в том, чтобы найти тройку {X, Y, Z} такую, что наименьшее общее кратное X , Y и Z меньше или равно N/2 , а сумма X , Y , и Z равно N . Если существует несколько ответов, то выведите любой из них.
Примеры:
Input: N = 8
Output: 4 2 2
Explanation:
One possible triplet is {4, 2, 2}. The sum of all the integers is equal to (4+2+2 = 8) and LCM is equal 4 which is equal to N/2( =4).Input: N = 5
Output: 1 2 2
Explanation:
One possible triplet is {1, 2, 2}. The sum of all the integers is equal to (1+2+2 = 5) and LCM is equal 2 which is equal to N/2( =2).
Подход: Проблема может быть решена на основе следующих фактов:
Suppose, N = X+Y+Z, then:
- If N is odd then either any one of X, Y or Z is odd or all three are odd numbers.
- If N is even, then all numbers must be even.
- Therefore, the idea is to include minimum possible value in the answer according to the above facts which will decrease the LCM of X, Y and Z.
Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте 3 переменные x, y и z как 0 , чтобы сохранить значения триплета.
- Если N%2 не равно 0 , т. е. N нечетно, выполните следующие шаги:
- Если N нечетно, по крайней мере один из x, y или z должен быть нечетным, а LCM x, y, z в худшем случае равен N/2 .
- Установите значение x и y равным N/2 , а значение z равным 1.
- В противном случае, если N%4 не равно 0, то значение z может быть равно 2 , а значения x и y могут быть равны N/2-1. В противном случае значение x может быть N/2 , а значение y и z может быть N/4.
- После выполнения вышеуказанных шагов выведите значения x, y и z.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(1)
Вспомогательное пространство: O(1)