Find triplet (A, B, C) such that LCM(A, B) + LCM(A, C) + LCM(B, C) equals N
Given an integer N. Find a triplet let say {A, B, C} such that LCM(A, B) + LCM(B, C) + LCM(A, C) = N. If no possible triplets are there, output -1 instead.
Examples:
Input: N = 1
Output: -1
Explanation: No possible triplets are there.Input: N = 15
Output: 5 5 5
Explanation: LCM(5, 5) + LCM(5, 1) + LCM(5, 1) = 5 + 5 + 5 = 15.
Observations:
Observation 1: If
N
is divisible by3
, the triplet can be {N/3, N/3, N/3}
. For example, ifN
is12
, the triplet is {4, 4, 4}.
Since,LCM(4, 4) + LCM(4, 4) + LCM(4, 4) = (4 + 4 + 4) = 12
.Observation 2: If (N <= 2), we will have our answer as -1. Because the minimum value of expression LCM(A, B) + LCM(B, C) + LCM(A, C) can be 3.
Observation 3: For value of N, which are perfect power of 2, no solution exists for them.
Proof:
- Let’s take 3 integers A, B and C and consider GCD(A, B, C) = G.
- Now, if we calculate the pairwise GCD for every pair of numbers:
- GCD(A, B) = G * X
- GCD(A, C) = G * Y
- GCD(B, C) = G * Z, where X, Y and Z will be pairwise co-prime.
- Further, it can be seen that
- A = G * X * Y * C1
- B = G * X * Z * C2
- C = G * Y * Z * C3, where C1, C2 and C3 are also co-prime.
- Then, LCM(A, B) + LCM(B, C) + LCM(C, A) = G * X * Y * Z * (C1 * C2 + C2 * C3 + C3 * C1), as we know that C1, C2 and C3 are pairwise coprime, therefore at most one of C1, C2 and C3 can be even. Therefore, LCM (A, B) + LCM (B, C) + LCM (C, A) will have an odd factor, which is greater than 1. So, it concludes, it is not possible to be a power of 2 equivalent to thus equation.
Observation 4: If
N
is odd, the triplet can always be {1, 1, (N - 1)/2}
. For example, ifN
is17
, the triplet is {1, 1, 8}.
Since, {LCM (1, 1) + LCM (1, 8) + LCM (1, 8)} = (1 + 8 + 8) = 17
.Final Observation: Now we are only left with elements that not divisible by 3 and are even for example 4, 8, 10…. and so on. For numbers that are not divisible by
3
, are even, and are not powers of2
, we can find the first set bit (Least Significant Bit) in their binary representation and calculate triplet as {1, (1<<bit), (N-(1<<bit))/2}
. For example, for N =10
(binary representation1010
), the valid triplet is {1, 2, 4}
.
Step-by-step algorithm:
- If (N <= 2)
- Output -1.
- If (N is divisible by 3)
- Output triplet as {N/3, N/3, N/3}.
- If (N is odd)
- Output triplet as {1, 1, N/2}.
- Else
- If (N is power of 2)
- Output -1
- Else
- Find LSB (Least Significant bit of N).
- Output triplet as {
1, (1<<bit), (N-(1<<bit))/2}
.
- If (N is power of 2)
Below is the implementation of the approach:
C++
#include <iostream> using namespace std; // Function to print triplet void Find_triplet( int N) { // If N is less than or equal to 2 then // no possible triplet is there if (N <= 2) { cout << -1 << endl; return ; } // If N is a multiple of 3 if (N % 3 == 0) { cout << " " << N / 3 << " " << N / 3 << " " << (N / 3) << endl; return ; } // If N is odd if (N % 2 == 1) { cout << " " << 1 << " " << 1 << " " << (N / 2) << endl; return ; } else { if ((N & (N - 1)) == 0) { cout << -1 << endl; } else { // Variable to store Least significant bit long long LSB = 2; while ((LSB & N) == 0) { LSB *= 2; } cout << 1 << " " << LSB << " " << (N - LSB) / 2 << endl; } } } // Driver Function int main() { // Input int N = 15; // Function call Find_triplet(N); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Input int N = 15 ; // Function_call Find_triplet(N); } // Function to print triplet public static void Find_triplet( int N) { // If N is less than or equal to 2 then // no possible triplet is there if (N <= 2 ) { System.out.println(- 1 ); return ; } // If N is a multiple of 3 if (N % 3 == 0 ) { System.out.println( " " + N / 3 + " " + N / 3 + " " + (N / 3 )); return ; } // If N is odd if (N % 2 == 1 ) { System.out.println( " " + 1 + " " + 1 + " " + (N / 2 )); return ; } else { if ((N & (N - 1 )) == 0 ) { System.out.println(- 1 ); } else { // Variable to store Least significant bit long LSB = 2 ; while ((LSB & N) == 0 ) { LSB *= 2 ; } System.out.println( 1 + " " + LSB + " " + (N - LSB) / 2 ); } } } } |
Python3
def find_triplet(N): # If N is less than or equal to 2, no possible triplet exists if N < = 2 : print ( - 1 ) return # If N is a multiple of 3, print a triplet with equal values if N % 3 = = 0 : print (f " {N // 3} {N // 3} {N // 3}" ) return # If N is odd, print a triplet with one 1 and two equal values if N % 2 = = 1 : print (f " {1} {1} {N // 2}" ) return else : # If N is not a power of 2, find the Least Significant Bit (LSB) if N & (N - 1 ) = = 0 : print ( - 1 ) else : LSB = 2 while LSB & N = = 0 : LSB * = 2 # Shift LSB to the left until it represents the LSB of N # Print a triplet where the first element is 1, the second element is the LSB, # and the third element is half of the difference between N and LSB print (f " {1} {LSB} {(N - LSB) // 2}" ) # Driver code if __name__ = = "__main__" : N = 15 find_triplet(N) |
C#
using System; class GFG { // Function to print triplet static void FindTriplet( int N) { // If N is less than or equal to 2 then // no possible triplet is there if (N <= 2) { Console.WriteLine(-1); return ; } // If N is a multiple of 3 if (N % 3 == 0) { Console.WriteLine($ " {N / 3} {N / 3} {N / 3}" ); return ; } // If N is odd if (N % 2 == 1) { Console.WriteLine($ " 1 1 {N / 2}" ); return ; } else { if ((N & (N - 1)) == 0) { Console.WriteLine(-1); } else { // Variable to store Least significant bit long LSB = 2; while ((LSB & N) == 0) { LSB *= 2; } Console.WriteLine($ " 1 {LSB} {(N - LSB) / 2}" ); } } } // Driver Function static void Main() { // Input int N = 15; // Function call FindTriplet(N); } } |
Javascript
<script> // Function to print triplet function findTriplet(N) { // If N is less than or equal to 2 then // no possible triplet is there if (N <= 2) { console.log(-1); return ; } // If N is a multiple of 3 if (N % 3 === 0) { console.log(` ${N / 3} ${N / 3} ${N / 3}`); return ; } // If N is odd if (N % 2 === 1) { console.log(` 1 1 ${N / 2}`); return ; } else { if ((N & (N - 1)) === 0) { console.log(-1); } else { // Variable to store Least significant bit let LSB = 2; while ((LSB & N) === 0) { LSB *= 2; } console.log(` 1 ${LSB} ${(N - LSB) / 2}`); } } } // Driver Function // Input const N = 15; // Function call findTriplet(N); </script> |
5 5 5
Time Complexity: O(LogN), As we are finding least significant bit of N.
Auxiliary Space: O(1)
Contact Us