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 fractionsvoid find_numbers(int N){ // Base condition if (N == 1) { cout << -1; } // For N > 1 else { cout << N << " " << N + 1 << " " << N * (N + 1); }}// Driver codeint main(){ int N = 5; find_numbers(N); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to find the required fractionsstatic 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 codepublic 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 approachusing System; class GFG {// Function to find the required fractionsstatic 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 codepublic 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
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!