Represent (2 / N) as the sum of three distinct positive integers of the form (1 / m)
Given a positive integer N, the task is to represent the fraction 2 / N as the sum of three distinct positive integers of the form 1 / m i.e. (2 / N) = (1 / x) + (1 / y) + (1 / z) and print x, y and z.
Examples:
Input: N = 3
Output: 3 4 12
(1 / 3) + (1 / 4) + (1 / 12) = ((4 + 3 + 1) / 12)
= (8 / 12) = (2 / 3) i.e. 2 / N
Input: N = 28
Output: 28 29 812
Approach: It can be easily inferred that for N = 1, there will be no solution. For N > 1, (2 / N) can be represented as (1 / N) + (1 / N) and the problem gets reduced to representing it as a sum of two fractions. Now, find the difference between (1 / N) and 1 / (N + 1) and get the fraction 1 / (N * (N + 1)). Therefore, the solution is (2 / N) = (1 / N) + (1 / (N + 1)) + (1 / (N * (N + 1))) where x = N, y = N + 1 and z = N * (N + 1).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the required fractions void find_numbers( int N) { // Base condition if (N == 1) { cout << -1; } // For N > 1 else { cout << N << " " << N + 1 << " " << N * (N + 1); } } // Driver code int main() { int N = 5; find_numbers(N); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to find the required fractions static void find_numbers( int N) { // Base condition if (N == 1 ) { System.out.print(- 1 ); } // For N > 1 else { System.out.print(N + " " + (N + 1 ) + " " + (N * (N + 1 ))); } } // Driver code public static void main(String []args) { int N = 5 ; find_numbers(N); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to find the required fractions def find_numbers(N) : # Base condition if (N = = 1 ) : print ( - 1 , end = ""); # For N > 1 else : print (N, N + 1 , N * (N + 1 )); # Driver code if __name__ = = "__main__" : N = 5 ; find_numbers(N); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to find the required fractions static void find_numbers( int N) { // Base condition if (N == 1) { Console.Write(-1); } // For N > 1 else { Console.Write(N + " " + (N + 1) + " " + (N * (N + 1))); } } // Driver code public static void Main(String []args) { int N = 5; find_numbers(N); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript implementation of the approach // Function to find the required fractions function find_numbers(N) { // Base condition if (N == 1) { document.write(-1); } // For N > 1 else { document.write(N + " " + (N + 1) + " " + (N * (N + 1))); } } // Driver code var N = 5; find_numbers(N); // This code is contributed by gauravrajput1 </script> |
5 6 30
Time Complexity: O(1), since no loop is used all operations takes constant time to perform all operations
Auxiliary Space: O(1), since no extra array is used hence space taken up by the algorithm is constant