≤ a/b is 1/⌈b/a⌉ where ⌈⌉ is the ceiling function.

Approach

Find the largest unit fraction: Calculate ceiling(b/a) to get the denominator of the largest unit fraction ≤ a/b
Subtract this unit fraction: Update the fraction to a/b - 1/ceiling(b/a)
Simplify the remainder: Reduce the resulting fraction to its simplest form
Repeat: Continue until the numerator becomes 1
Handle edge cases: Ensure proper fraction (a < b) and handle when a = 1

Code

[{"language":"C++","code":"#include <vector>\n#include <string>\n#include <algorithm>\n#include <cmath>\n\nclass Solution {\npublic:\n    std::vector<int> egyptianFraction(int a, int b) {\n        std::vector<int> result;\n        \n        // Reduce to lowest terms first\n        int g = gcd(a, b);\n        a /= g;\n        b /= g;\n        \n        while (a != 0) {\n            // Find ceiling of b/a\n            int unitDenom = (b + a - 1) / a;  // Ceiling division\n            result.push_back(unitDenom);\n            \n            // Update fraction: a/b - 1/unitDenom\n            // = (a * unitDenom - b) / (b * unitDenom)\n            a = a * unitDenom - b;\n            b = b * unitDenom;\n            \n            // Reduce to lowest terms\n            if (a != 0) {\n                int g = gcd(a, b);\n                a /= g;\n                b /= g;\n            }\n        }\n        \n        return result;\n    }\n    \n    std::string egyptianFractionString(int a, int b) {\n        std::vector<int> fractions = egyptianFraction(a, b);\n        std::string result = \"\";\n        \n        for (size_t i = 0; i < fractions.size(); i++) {\n            if (i > 0) result += \" + \";\n            result += \"1/\" + std::to_string(fractions[i]);\n        }\n        \n        return result;\n    }\n    \nprivate:\n    int gcd(int a, int b) {\n        while (b != 0) {\n            int temp = b;\n            b = a % b;\n            a = temp;\n        }\n        return a;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;string></span></span>\n&

Related Tags