Given a positive integer N, the task is to find a triple of three distinct positive integers (X, Y, Z) such that X + Y + Z = N and X = GCD (Y, Z).
Example:
Input: N = 12
Output:1 2 9
Explanation: The triplet (1, 2, 9) is set of distinct integers such that 1 + 2 + 9 = 12 and 1 = GCD(2, 9).Input: N = 5675
Output:1 3 5671
Naive Approach: The basic idea is to iterate to find all possible triplets of (X, Y, Z) with sum N and for each triplet, check if GCD(Y, Z) = X.
Code-
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find a triplet (X, Y, Z)// of distinct integers with their sum// as N and GCD(Y, Z) = Xvoid printTriplet(int N){ for(int i=1;i<N;i++){ for(int j=i+1;j<N;j++){ for(int k=j+1;k<N;k++){ if(i+j+k==N && __gcd(j,k)==i){ cout<<i<<" "<<j<<" "<<k<<endl; return; } } } }}// Driver Codeint main(){ int N = 5875; printTriplet(N); return 0;} |
Java
import java.util.*;class GFG { // Function to find a triplet (X, Y, Z) // of distinct integers with their sum // as N and GCD(Y, Z) = X static void printTriplet(int N) { for (int i = 1; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { if (i + j + k == N && gcd(j, k) == i) { System.out.println(i + " " + j + " " + k); return; } } } } } // Function to calculate GCD of two numbers static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // Driver Code public static void main(String[] args) { int N = 5875; printTriplet(N); }} |
Python3
import math# Function to find a triplet (X, Y, Z)# of distinct integers with their sum# as N and GCD(Y, Z) = Xdef printTriplet(N): for i in range(1, N): for j in range(i+1, N): for k in range(j+1, N): if i+j+k == N and math.gcd(j, k) == i: print(i, j, k) return# Driver Codeif __name__ == "__main__": N = 5875 printTriplet(N) |
C#
using System;class MainClass { // Function to find a triplet (X, Y, Z) // of distinct integers with their sum // as N and GCD(Y, Z) = X static void PrintTriplet(int N) { for (int i = 1; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { if (i + j + k == N && gcd(j, k) == i) { Console.WriteLine(i + " " + j + " " + k); return; } } } } } static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Driver Code public static void Main(string[] args) { int N = 5875; PrintTriplet(N); }} |
Javascript
// Function to find a triplet (X, Y, Z)// of distinct integers with their sum// as N and GCD(Y, Z) = Xfunction printTriplet(N) { for (let i = 1; i < N; i++) { for (let j = i + 1; j < N; j++) { for (let k = j + 1; k < N; k++) { if (i + j + k == N && gcd(j, k) == i) { console.log(i, j, k); return; } } } }}// Function to find the greatest common divisor (GCD) of two numbersfunction gcd(a, b) { if (b == 0) return a; return gcd(b, a % b);}// Driver Codelet N = 5875;printTriplet(N); |
Output
1 5 5869
Time Complexity: O(N3*logN),logN for finding GCD, and N3 for three “for” loops
Auxiliary space: O(1)
Efficient Approach: The above approach can be further optimized using the observation that for any given N, there are the following three cases:
- Case 1: If N is even then, a valid triplet is (1, N/2, N/2 -1).
- Case 2: If N is odd and (N/2) is even then, a valid triplet is (1, N/2 + 1, N/2 -1).
- Case 3: If N is odd and (N/2) is also odd then, a valid triplet is (1, N/2 – 2, N/2 + 2).
Hence, for any given N, identify the case and print its respective triplet.
Below is the implementation of the approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find a triplet (X, Y, Z)// of distinct integers with their sum// as N and GCD(Y, Z) = Xint printTriplet(int N){ // Case 1 where N is even if (N % 2 == 0) { cout << 1 << " " << (N / 2) << " " << (N / 2) - 1; } else { // Case 2 where N is Odd // and N/2 is even if ((N / 2) % 2 == 0) { cout << 1 << " " << (N / 2) - 1 << " " << (N / 2) + 1; } // Case 3 where N is Odd // and N/2 is also odd else { cout << 1 << " " << (N / 2) - 2 << " " << (N / 2) + 2; } }}// Driver Codeint main(){ int N = 5875; printTriplet(N); return 0;} |
Java
// Java program of the above approachimport java.util.*;class GFG { // Function to find a triplet (X, Y, Z) // of distinct integers with their sum // as N and GCD(Y, Z) = X static void printTriplet(int N) { // Case 1 where N is even if (N % 2 == 0) { System.out.print(1 + " " + (N / 2) + " " + ((N / 2) - 1)); } else { // Case 2 where N is Odd // and N/2 is even if ((N / 2) % 2 == 0) { System.out.print(1 + " " + ((N / 2) - 1) + " " + ((N / 2) + 1)); } // Case 3 where N is Odd // and N/2 is also odd else { System.out.print(1 + " " + ((N / 2) - 2) + " " + ((N / 2) + 2)); } } } // Driver Code public static void main(String[] args) { int N = 5875; printTriplet(N); }}// This code is contributed by 29AjayKumar |
Python3
# python3 program of the above approach# Function to find a triplet (X, Y, Z)# of distinct integers with their sum# as N and GCD(Y, Z) = Xdef printTriplet(N): # Case 1 where N is even if (N % 2 == 0): print(f"{1} {(N / 2)} {(N / 2) - 1}") else: # Case 2 where N is Odd # and N/2 is even if ((N // 2) % 2 == 0): print(f"{1} {(N // 2) - 1} {(N // 2) + 1}") # Case 3 where N is Odd # and N/2 is also odd else: print(f"{1} {(N // 2) - 2} {(N // 2) + 2}")# Driver Codeif __name__ == "__main__": N = 5875 printTriplet(N)# This code is contributed by rakeshsahni |
C#
// C# program of the above approachusing System;class GFG{// Function to find a triplet (X, Y, Z)// of distinct integers with their sum// as N and GCD(Y, Z) = Xstatic void printTriplet(int N){ // Case 1 where N is even if (N % 2 == 0) { Console.Write(1 + " " + (N / 2) + " " + ((N / 2) - 1)); } else { // Case 2 where N is Odd // and N/2 is even if ((N / 2) % 2 == 0) { Console.Write(1 + " " + ((N / 2) - 1) + " " + ((N / 2) + 1)); } // Case 3 where N is Odd // and N/2 is also odd else { Console.Write(1 + " " + ((N / 2) - 2) + " " + ((N / 2) + 2)); } }}// Driver Codepublic static void Main(){ int N = 5875; printTriplet(N);}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript code for the above approach // Function to find a triplet (X, Y, Z) // of distinct integers with their sum // as N and GCD(Y, Z) = X function printTriplet(N) { // Case 1 where N is even if (N % 2 == 0) { document.write(1 + " " + Math.floor(N / 2) + " " + (Math.floor(N / 2) - 1)); } else { // Case 2 where N is Odd // and N/2 is even if ((N / 2) % 2 == 0) { document.write(1 + " " + (Math.floor(N / 2) - 1) + " " + (Math.floor(N / 2) + 1)); } // Case 3 where N is Odd // and N/2 is also odd else { document.write(1 + " " + (Math.floor(N / 2) - 2) + " " + (Math.floor(N / 2) + 2)); } } } // Driver Code let N = 5875; printTriplet(N); // This code is contributed by Potta Lokesh </script> |
Output
1 2935 2939
Time Complexity: O(1)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
