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 = 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).
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++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find a triplet with the // sum equal to N and LCM less than or // equal to N void validTriplet( int N) { // Stores the triplets int x, y, z; // If N is odd if ((N % 2) != 0) { x = N / 2; y = N / 2; z = 1; } // If N is even else { // If N is not a multiple of 4 if ((N % 4) != 0) { x = (N / 2) - 1; y = (N / 2) - 1; z = 2; } // If N is a multiple of 4 else { x = N / 2; y = N / 4; z = N / 4; } } // Finally, print the answer cout << x << " " << y << " " << z << '\n' ; } // Driver Code int main() { // Given Input int N = 5; // Function Call validTriplet(N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find a triplet with the // sum equal to N and LCM less than or // equal to N static void validTriplet( int N) { // Stores the triplets int x, y, z; // If N is odd if ((N % 2 ) != 0 ) { x = N / 2 ; y = N / 2 ; z = 1 ; } // If N is even else { // If N is not a multiple of 4 if ((N % 4 ) != 0 ) { x = (N / 2 ) - 1 ; y = (N / 2 ) - 1 ; z = 2 ; } // If N is a multiple of 4 else { x = N / 2 ; y = N / 4 ; z = N / 4 ; } } // Finally, print the answer System.out.print(x + " " + y + " " + z); } // Driver Code public static void main(String[] args) { // Given Input int N = 5 ; // Function Call validTriplet(N); } } // This code is contributed by Potta Lokesh |
Python3
# Function to find a triplet with the # sum equal to N and LCM less than or # equal to N def validTriplet(N): # If N is odd if (N % 2 ) ! = 0 : x = N / / 2 y = N / / 2 z = 1 # if N is even else : # If N is not a multiple of 4 if (N % 4 ) ! = 0 : x = N / / 2 - 1 y = N / / 2 - 1 z = 2 # if N is multiple of 4 else : x = N / / 2 y = N / / 4 z = N / / 4 # Print the result print ( str (x) + " " + str (y) + " " + str (z)) # Driver code N = 5 validTriplet(N) # This code is contributed by Parth Manchanda |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find a triplet with the // sum equal to N and LCM less than or // equal to N static void validTriplet( int N) { // Stores the triplets int x, y, z; // If N is odd if ((N % 2) != 0) { x = N / 2; y = N / 2; z = 1; } // If N is even else { // If N is not a multiple of 4 if ((N % 4) != 0) { x = (N / 2) - 1; y = (N / 2) - 1; z = 2; } // If N is a multiple of 4 else { x = N / 2; y = N / 4; z = N / 4; } } // Finally, print the answer Console.Write(x + " " + y + " " + z ); } // Driver Code public static void Main() { // Given Input int N = 5; // Function Call validTriplet(N); } } // This code is contributed by ipg2016107. |
Javascript
<script> // Java program for the above approach // Function to find a triplet with the // sum equal to N and LCM less than or // equal to N function validTriplet(N) { // Stores the triplets var x, y, z; // If N is odd if ((N % 2) == 0) { x = N / 2; y = N / 2; z = 1; } // If N is even else { // If N is not a multiple of 4 if ((N % 4) != 0) { x = (N / 2) - 1; y = (N / 2) - 1; z = 1; } // If N is a multiple of 4 else { x = N / 2; y = N / 4; z = N / 4; } } // Finally, print the answer document.write(x + " " + y + " " + z); } // Driver Code // Given Input var N = 4; // Function Call validTriplet(N); // This code is contributed by shivanisinghss2110 </script> |
2 2 1
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us