Scenario

For this activity, we will be building a greedy algorithm to compute Egyptian fractions. Every positive fraction can be represented as a sum of unique unit fractions. A fraction is a unit fraction if its numerator is one and its denominator is a positive integer. For example, 1/3 is a unit fraction. Such a representation, for example, a sum of unique unit fractions, is called an Egyptian fraction, since it was used by the ancient Egyptians.

For example, the Egyptian fraction representation of 2/3 is 1/2 + 1/6. The Egyptian fraction representation of 6/14 is 1/3 + 1/11 + 1/231.

Aim

To implement a greedy algorithm to compute Egyptian fractions, as described previously.

Prerequisites

• Implement the build method of the EgyptianFractions class, which returns a list of denominators for the Egyptian fraction representation, in increasing order, which is available on GitHub at: 
  https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson4/activity/egyptian/EgyptianFractions.java
• Assume that the denominator is always larger than the numerator, and that the returned denominators always fit in a Long

Steps for Completion

1. Check whether the numerator divides the denominator without leaving a remainder, and that we're left with a single fraction
2. If not, find the greatest possible unit fraction, subtract it from the original fraction, and recur on the remaining fraction

In this first section, we introduced the greedy paradigm of algorithm design using the activity selection problem as a running example. We introduced the two properties a problem must observe to be optimally solved by a greedy algorithm: optimal substructure and greedy choice. To gain intuition about the applicability of greedy algorithms, we later explored two other problems that are solvable by a greedy approach: Huffman coding and Egyptian fractions.