Greedy Algorithm For Egyptian Fraction In C++

Introduction

Egyptian fractions offer a unique method for representing rational numbers through the summation of unit fractions with a numerator of 1. This method was utilized by ancient Egyptians in their hieroglyphic representations of fractions. Each ancient Egyptian fraction was distinct, ensuring that no two fractions were identical.

In this post, we will explore the concept of the Egyptian fraction conundrum and subsequently illustrate the process of constructing a greedy algorithm in C++ that is capable of ascertaining if a specified rational number is representable as an Egyptian fraction.

Problem Statement

Representing a rational number n/d as the sum of distinct unit fractions involves breaking it down into a series of fractions where the numerator is 1 and the denominator varies. This process is known as Egyptian fraction representation.

For instance, consider 4/7 as the fraction to analyze. The Egyptian fraction form of 4/7 is 1/2 + 1/14.

Greedy Algorithm

A greedy algorithm is a problem-solving technique that focuses on selecting the most advantageous choice at each step, aiming to achieve the best immediate outcome with the expectation of optimizing overall results. This strategy prioritizes the current best option without taking into account potential future impacts, with the objective of maximizing results in the present moment under the belief that it will lead to the most beneficial overall solution.

The greedy approach to finding Egyptian fractions functions based on a simple concept: during each step, pick the most substantial possible unit fraction that is less than the remaining proper fraction.

There are these steps to implement the Greedy Algorithm.

Steps for Greedy Algorithm:

• ✅ Get an empty result; we begin with 0.
• ✅ Get the largest unit fraction: In this step, we will find the unit fraction that is not greater than the given fraction at each step. It can be calculated as the ceiling of the reciprocal of the remaining fraction. It implies that we divide 1 by the remaining fraction and then round off to the nearest integer.
• ✅ Add the unit fraction to the result: After finding out the largest unit fraction, add it to our list of results.
• ✅ Update the remaining fraction: Subtract the numerator from it and multiply the result by the denominator to eliminate the information discovered in the second step above.
• ✅ Continue till there is no more residual. This should be done until there is no more leftover.

Program:

Let's consider an example to demonstrate the Greedy Algorithm for representing Egyptian Fractions in the C++ programming language.

#include <iostream>
#include <vector>

using namespace std;

vector<int> findEgyptianFraction(int numerator, int denominator) {
    vector<int> result;

    while (numerator != 0) {
        // Find the largest unit fraction less than or equal to numerator/denominator
        int unit = (denominator + numerator - 1) / numerator;

        // Add the unit fraction to the result
        result.push_back(unit);

        // Update the numerator and denominator for the next iteration
        numerator = numerator * unit - denominator;
        denominator = denominator * unit;

    }

    return result;
}

void printEgyptianFraction(int numerator, int denominator) {
    vector<int> egyptianFraction = findEgyptianFraction(numerator, denominator);
    int n = egyptianFraction.size();

    // Printing the Egyptian fraction representation
    for (int i = 0; i < n; i++) {
        cout << "1/" << egyptianFraction[i];
        if (i != n - 1) {
            cout << " + ";
        }
    }
    cout << endl;
}

int main() {
    int numerator, denominator;
    cout << "Enter the numerator: ";
    cin >> numerator;
    cout << "Enter the denominator: ";
    cin >> denominator;

    cout << "Egyptian Fraction Representation: ";
    printEgyptianFraction(numerator, denominator);

    return 0;
}

Output:

Enter the numerator: 4
Enter the denominator: 7
Egyptian Fraction Representation: 1/2 + 1/14

Explanation:

The user enters the numerator and denominator that will make up an Egyptian fraction .

• ✅ findEgyptianFraction function: This function takes as input a numerator and denominator pair of numbers and returns a vector that contains all the unit fractions that can form an Egyptian fraction. It involves the implementation of the greedy algorithm above.
• ✅ printEgyptianFraction function: This function also receives a numerator and denominator pair, finds the Egyptian fraction representation using findEgyptianFraction, and then displays it in the 1/x + 1/y +...form.
• ✅ In the Main Function, we request that users type their numerators and denominators.
• ✅ It calls the printEgyptianFraction function to find and display the Egyptian fractions on the screen of the given fractions by the user.

Time and Space Complexities:

• ✅ Time Complexity: The algorithm's time complexity is defined as O(d), where d represents a specific denominator. As the denominator increases, the number of iterations required also increases in direct proportion.
• ✅ Space Complexity: This challenge pertains to the extra storage space needed for constants. Its space complexity is O(d), along with the necessity for memory allocation that accurately represents the output derived from employing an Egyptian fraction.

Advantages of Greedy Algorithm:

There are several advantages of the Greedy Algorithm . Some main advantages of the Greedy Algorithm are as follows:

• ✅ Efficiency: Greedy algorithms often have efficiency in terms of time complexity, especially compared to brute force or exhaustive search methods. It makes locally optimal choices at each step, leading to a solution that is usually close to the optimum.
• ✅ Simplicity: The greedy algorithms are quite simple when it comes to implementation and understanding. They follow a direct way of choosing the best possible because they continue without considering the whole system. Simplicity at this level makes them accessible to programmers with different levels of expertise.
• ✅ Space Complexity: Generally, greedy algorithms require less space than other approaches. Such algorithms tend not to store huge volumes of data or use complex data structures, thereby utilising memory efficiently.
• ✅ Optimality in Some Cases: Greedy algorithms are not always globally optimal, though they can be used to get optimality for some specific problems. For Egyptian fractions, the greedy algorithm typically yields an approximation that is somewhere near an optimal representation using the fewest unit fractions possible.
• ✅ Incremental Solution Construction: Greedy algorithms build solutions in a progressive way by making choices that are locally optimal at each stage. For instance, if it is possible to partition the problem into smaller sub-problems that can be solved independently, this method of incrementality may be useful.

Disadvantages of Greedy Algorithm:

There are several disadvantages of the Greedy Algorithm . Some main disadvantages of the Greedy Algorithm are as follows:

• ✅ Perfection is not guaranteed: There are situations when greedy algorithms fail to give an optimal global solution. They can miss a better overall solution that would require immediate gains to be surrendered for long-term benefits because they make the correct local moves at each step.
• ✅ Local Choices Dependence: The greedy algorithms depend heavily on the premise that selecting the most preferable option will yield the best outcome globally at any given point. However, it does not hold true for all problems with intricate dependencies or constraints.
• ✅ Difficulties in Backtracking: Once it makes an error while picking alternatives at random during operation, it cannot easily go back and rectify them from there. This limitation is observed when irreversible decisions made earlier on result in suboptimal or invalid outcomes.
• ✅ Sensitive to Input Order: The order of elements or choices considered in a greedy algorithm can drastically affect its output. Even slight changes in input order can result in wildly different solutions, rendering the behaviour of the algorithm unpredictable to some extent.

Conclusion:

In summary, we have delved into the Egyptian fraction conundrum and then applied a greedy algorithm implemented in C++ to discover an Egyptian fraction representation for any given rational number. These fractions, which were utilized by ancient Egyptians in their notation system, offer a distinct approach to representing rational numbers. The greedy algorithm efficiently determines the representation by selecting the largest possible unit fraction at each step until no remainder remains. An analysis of the time and space complexity sheds light on the efficiency and resource requirements of this approach. Ultimately, this investigation offers insight into the historical significance of Egyptian fractions and illustrates how greedy algorithms can be employed in practical computer programming scenarios.