Log inSign up
mediumGeeksforGeeksNot Started

Egyptian Fraction

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two positive integers nr (numerator) and dr (denominator) representing a fraction nr / dr (where nr < dr), express this fraction as a sum of distinct unit fractions (fractions of the form 1 / d where d is a positive integer).

Return the denominators of these unit fractions.

Example 1 · Example 1: 6 / 14:

Input: nr = 6, dr = 14
Output: [3, 11, 231]
Explanation: 6/14 simplifies to 3/7. 1. ceil(7 / 3) = 3 -> Unit fraction is 1/3. 2. Remainder: 3/7 - 1/3 = (9 - 7) / 21 = 2/21. 3. ceil(21 / 2) = 11 -> Unit fraction is 1/11. 4. Remainder: 2/21 - 1/11 = (22 - 21) / 231 = 1/231. 5. Denominators: [3, 11, 231].

Example 2 · Example 2: 2 / 3:

Input: nr = 2, dr = 3
Output: [2, 6]
Explanation: ceil(3 / 2) = 2 -> 1/2. 2/3 - 1/2 = 1/6 -> 1/6. Denominators: [2, 6].

Constraints:

  • 1 <= nr < dr <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand Fibonacci's greedy decomposition proof for Egyptian fractions.
  • Prevent integer overflow using GCD reduction.
  • Implement the algorithm across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Decompose a rational number into sum of unit fractions.
  • Greedy selection of the largest permissible piece.
  • Arithmetic operations over fractions.

Algorithmic Decision Tree:

  • Compute unit denominator d = Math.ceil(dr / nr).
  • Append d to result.
  • Update remainder: nr = nr * d - dr, dr = dr * d.
  • Simplify by greatest common divisor (GCD).

Connected Patterns:

Fractional KnapsackMinimum Number of CoinsInteger to Roman

1. Brute Force — Linear Denominator Scan

Intuition

Test integers d = 2, 3, 4, ... sequentially. If 1/d <= nr/dr, append d, subtract 1/d from current fraction, and continue with d + 1.

When to apply: When denominators are very small.

Algorithm

  1. Step 1: Initialize d = 2, result = [].
  2. Step 2: While nr > 0: if dr <= nr * d, append d and update nr = nr * d - dr, dr = dr * d.
  3. Step 3: Increment d++.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 long long gcd(long long a, long long b) {
9 return b == 0 ? a : gcd(b, a % b);
10 }
11public:
12 vector<long long> egyptianFraction(long long nr, long long dr) {
13 vector<long long> res;
14 long long d = 2;
15 while (nr > 0) {
16 if (dr <= nr * d) {
17 res.push_back(d);
18 nr = nr * d - dr;
19 dr = dr * d;
20 long long g = gcd(nr, dr);
21 nr /= g;
22 dr /= g;
23 }
24 d++;
25 }
26 return res;
27 }
28};
29
30int main() {
31 Solution sol;
32 auto res = sol.egyptianFraction(2, 3);
33 for (auto d : res) cout << d << " ";
34 cout << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(dr * steps) — Linear increment of d until matching denominator.
  • Space complexity: O(steps) — Result array storage.

Why Brute Force Doesn't Scale:

Linear stepping from 2 upwards times out for denominators in the thousands. Greedy jumping to ceil(dr / nr) takes logarithmic steps.

For 6/14: takes only 3 steps [3, 11, 231] instead of checking 231 numbers.

2. Better — Recursive Greatest Common Divisor Reduction

Intuition

Base cases: if dr % nr == 0, append dr / nr and stop. Otherwise, d = dr / nr + 1. Append d, then recursively solve for remainder: (nr * d - dr) / (dr * d).

When to apply: When functional recursive formulation is preferred.

Algorithm

  1. Step 1: If nr == 0 or dr == 0, return.
  2. Step 2: If dr % nr == 0, append dr / nr and return.
  3. Step 3: d = dr / nr + 1. Append d.
  4. Step 4: Recurse on nr * d - dr and dr * d.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 long long gcd(long long a, long long b) {
9 return b == 0 ? a : gcd(b, a % b);
10 }
11
12 void solve(long long nr, long long dr, vector<long long>& res) {
13 if (nr == 0 || dr == 0) return;
14 if (dr % nr == 0) {
15 res.push_back(dr / nr);
16 return;
17 }
18 long long d = dr / nr + 1;
19 res.push_back(d);
20
21 long long nextNr = nr * d - dr;
22 long long nextDr = dr * d;
23 long long g = gcd(nextNr, nextDr);
24 solve(nextNr / g, nextDr / g, res);
25 }
26public:
27 vector<long long> egyptianFraction(long long nr, long long dr) {
28 vector<long long> res;
29 solve(nr, dr, res);
30 return res;
31 }
32};
33
34int main() {
35 Solution sol;
36 auto res = sol.egyptianFraction(6, 14);
37 for (auto d : res) cout << d << " ";
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(steps) — Strictly decreases numerator on each step.
  • Space complexity: O(steps) stack — Recursion call stack.

3. Optimal — Fibonacci's Iterative Greedy Algorithm

Intuition

While nr != 0, if dr % nr == 0, append dr / nr and break. Otherwise, d = dr / nr + 1. Append d to answer, update nr = nr * d - dr and dr = dr * d, then divide both by gcd(nr, dr). This is provably optimal and terminates in finite steps.

When to apply: Standard optimal solution for Egyptian Fraction.

Algorithm

  1. Step 1: Loop while nr > 0.
  2. Step 2: If dr % nr == 0: append dr / nr and break.
  3. Step 3: d = dr / nr + 1.
  4. Step 4: Append d to result.
  5. Step 5: nr = nr * d - dr, dr = dr * d.
  6. Step 6: Simplify nr and dr by their gcd.

Interactive Trace for Egyptian Fraction

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Compute d = ceil(3 / 2) = 2
Visual state
Values and pointers at this exact step
pointers
S
2
1/6
0
↑ first_unit
1
Check / comparison
d = ceil(3 / 2) = 2
Decision / next transition
Add denominator 2. New fraction: 2/3 - 1/2 = 1/6.
Why this step matters

Step 1: Compute d = ceil(3 / 2) = 2. Unit fraction 1/2. Subtract 1/2 from 2/3.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8 long long gcd(long long a, long long b) {
9 return b == 0 ? a : gcd(b, a % b);
10 }
11public:
12 vector<long long> egyptianFraction(long long nr, long long dr) {
13 vector<long long> res;
14 while (nr > 0) {
15 if (dr % nr == 0) {
16 res.push_back(dr / nr);
17 break;
18 }
19 long long d = dr / nr + 1;
20 res.push_back(d);
21 long long nextNr = nr * d - dr;
22 long long nextDr = dr * d;
23 long long g = gcd(nextNr, nextDr);
24 nr = nextNr / g;
25 dr = nextDr / g;
26 }
27 return res;
28 }
29};
30
31int main() {
32 Solution sol;
33 auto res = sol.egyptianFraction(6, 14);
34 for (auto d : res) cout << d << " ";
35 cout << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(steps) — The numerator strictly decreases at each step, guaranteeing termination in small number of steps.
  • Space complexity: O(1) auxiliary — Uses only scalar integers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Denominator SearchO(dr * steps)O(steps)Increment d from 2 upwards. If 1 / d <= nr / dr, take it and subtract.Linear stepping.
2.Better — Recursive Search / BacktrackingO(depth * branching)O(depth)Backtrack to find a combination of unit fractions with small denominators.Branching complexity.
3.Optimal — Fibonacci's Greedy AlgorithmOptimalO(steps)O(1) auxiliaryDirectly calculate d = ceil(dr / nr) in O(1). Subtract and reduce fraction by gcd. Strictly decreases numerator each step.Arithmetic on large integers.

Common Pitfalls & Crucial Edge Cases

Forgetting to divide by GCD

Denominators can balloon exponentially fast if not simplified by GCD at each step.

Integer division truncation

Using integer division dr / nr directly without + 1 produces 1/d > nr/dr, making remainder negative.

Crucial Edge Cases to Validate:

  • nr divides dr — Single step produces 1 / (dr / nr).
  • nr = 1 — Already a unit fraction; returns [dr].
  • Large intermediate products — Must use 64-bit BigInt/long to avoid overflow before GCD reduction.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the termination proof: nr' = nr * d - dr = nr * (floor(dr/nr) + 1) - dr = nr - (dr % nr) < nr.
  2. Because the numerator strictly decreases and is bounded below by 0, the algorithm must terminate.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the denominator chosen as ceil(dr / nr) = dr // nr + 1?

Back to DSA Sheet