Выведите триплет с суммой, равной N, и LCM не более N/2.

Опубликовано: 22 Сентября, 2022

Для данного положительного целого числа 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:

  1. If N is odd then either any one of X, Y or Z is odd or all three are odd numbers.
  2. If N is even, then all numbers must be even.
  3. 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ