Given two positive integers N and D representing a fraction as N/D, the task is to split the fraction into the sum of multiple fractions having numerator as 1.
Examples:
Input: n = 4, d = 5
Output: 1/2, 1/4, 1/20
Explanation: 1/2 + 1/4 + 1/20 = 4/5Input: n = 15, d = 16
Output: 1/2, 1/3, 1/10, 1/240
Approach: The idea is that all positive fractions of the form n/d can be written as a sum of distinct unit fractions. The answer can be found by removing largest unit fraction 1/x till the fraction reaches to zero where x can be found as ceil(d/n). After finding the unit fraction, update the fraction to n/d – 1/x so n changes to nx-d and d changes to dx at each step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to split the fraction into// distinct unit fractionvector<string> FractionSplit(long long n, long long d){ // To store answer vector<string> UnitFactions; // While numerator is positive while (n > 0) { // Finding x = ceil(d/n) long long x = (d + n - 1) / n; // Add 1/x to list of ans string s = "1/" + to_string(x); UnitFactions.push_back(s); // Update fraction n = n * x - d; d = d * x; } return UnitFactions;}// Driver Codeint main(){ // Given Input long long n = 13, d = 18; // Function Call auto res = FractionSplit(n, d); // Print Answer for (string s : res) cout << s << ", "; return 0;} |
Java
// Java program for the above approachimport java.util.Vector;public class GFG { // Function to split the fraction into // distinct unit fraction static Vector<String> FractionSplit(long n, long d) { // To store answer Vector<String> UnitFactions = new Vector<>(); // While numerator is positive while (n > 0) { // Finding x = ceil(d/n) long x = (d + n - 1) / n; // Add 1/x to list of ans String s = "1/" + String.valueOf(x); UnitFactions.add(s); // Update fraction n = n * x - d; d = d * x; } return UnitFactions; } // Driver code public static void main(String[] args) { // Given Input long n = 13, d = 18; // Function Call Vector<String> res = FractionSplit(n, d); // Print Answer for (String s : res) System.out.print(s + ", "); }}// This code is contributed by abhinavjain194 |
Python3
# Python program for the above approach# Function to split the fraction into# distinct unit fractiondef FractionSplit(n, d): # To store answer UnitFactions = [] # While numerator is positive while (n > 0): # Finding x = ceil(d/n) x = (d + n - 1) // n # Add 1/x to list of ans s = "1/" + str(x) UnitFactions.append(s); # Update fraction n = n * x - d; d = d * x return UnitFactions;# Driver Code# Given Inputn = 13;d = 18;# Function Callres = FractionSplit(n, d);# Print Answerfor s in res: print(s + ", ", end=" ");# This code is contributed by _saurabh_jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to split the fraction into// distinct unit fractionstatic List<string> FractionSplit(long n, long d){ // To store answer List<string> UnitFactions = new List<string>(); // While numerator is positive while (n > 0) { // Finding x = ceil(d/n) long x = (d + n - 1) / n; // Add 1/x to list of ans string s = "1/" + x.ToString(); UnitFactions.Add(s); // Update fraction n = n * x - d; d = d * x; } return UnitFactions;}// Driver codepublic static void Main(string[] args){ // Given Input long n = 13, d = 18; // Function Call List<string> res = FractionSplit(n, d); // Print Answer foreach(string s in res) Console.Write(s + ", ");}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approach// Function to split the fraction into// distinct unit fractionfunction FractionSplit(n, d) { // To store answer let UnitFactions = []; // While numerator is positive while (n > 0) { // Finding x = ceil(d/n) let x = Math.floor((d + n - 1) / n); // Add 1/x to list of ans let s = "1/" + String(x); UnitFactions.push(s); // Update fraction n = n * x - d; d = d * x; } return UnitFactions;}// Driver Code// Given Inputlet n = 13, d = 18;// Function Calllet res = FractionSplit(n, d);// Print Answerfor (let s of res) document.write(s + ", ");// This code is contributed by gfgking.</script> |
Output
1/2, 1/5, 1/45,
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!
