- Greedy, Mathematical

Print triplet with sum equal to N and LCM at most N/2

Given a positive integer N, the task is to find a triplet {X, Y, Z} such that the least common multiple of X, Y, and Z is less than or equal to N/2 and the sum of X, Y, and Z is equal to N. If there exist multiple answers, then print any of them.Examples:Input: N = 8Output: 4 2 2Explanation: 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 = 5Output: 1 2 2Explanation: 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).Approach: The problem can be solved based on the following facts: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. Follow the steps below to solve the problem:Initialize 3 variables x, y, and z as 0 to store the values of the triplet.If N%2 is not equal to 0 i.e, N is odd, then, perform the following steps:If N is odd, at least one out of x, y, or z should be odd, and the LCM of x, y, z is N/2 in the worst case.Set the value of x and y to N/2 and the value of z to 1.Otherwise, if N%4 is not equal to 0, then the value of z can be 2 and the values of x and y can be N/2-1. Otherwise, the value of x can be N/2 and the value of y and z can be N/4.After performing the above steps, print the values of x, y, and z.Below is the implementation of the above approach.C++#include using namespace std;  void validTriplet(int N){        int x, y, z;          if ((N % 2) != 0) {        x = N / 2;        y = N / 2;        z = 1;    }        else {                  if ((N % 4) != 0) {            x = (N / 2) – 1;            y = (N / 2) – 1;            z = 2;        }                  else {            x = N / 2;            y = N / 4;            z = N / 4;        }    }          cout