Repository: TheAlgorithms/Java
Pull request #5804 (2024-10-14 09:53:24)

feat: Add `EgyptianFraction` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5804?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 64.82%. Comparing base [(`9c76b30`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/9c76b30271535123ea30c0b39a46ccee6b302c6c?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`f6b8636`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f6b86362a08113c15a8d53dea74be33303d78aa5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5804      +/-   ##
============================================
+ Coverage     64.81%   64.82%   +0.01%     
- Complexity     4299     4301       +2     
============================================
  Files           599      600       +1     
  Lines         16764    16772       +8     
  Branches       3219     3220       +1     
============================================
+ Hits          10865    10873       +8     
  Misses         5455     5455              
  Partials        444      444              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5804?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 744e16db..98fbec62 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -321,6 +321,7 @@
             * [BinaryAddition](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/BinaryAddition.java)
             * [CoinChange](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/CoinChange.java)
             * [DigitSeparation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/DigitSeparation.java)
+            * [EgyptianFraction](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/EgyptianFraction.java)
             * [FractionalKnapsack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java)
             * [GaleShapley](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/GaleShapley.java)
             * [JobSequencing](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/JobSequencing.java)
@@ -351,6 +352,7 @@
             * [BinaryPow](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/BinaryPow.java)
             * [BinomialCoefficient](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/BinomialCoefficient.java)
             * [Ceil](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/Ceil.java)
+            * [ChineseRemainderTheorem](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/ChineseRemainderTheorem.java)
             * [CircularConvolutionFFT](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/CircularConvolutionFFT.java)
             * [CollatzConjecture](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/CollatzConjecture.java)
             * [Combinations](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/Combinations.java)
@@ -568,6 +570,8 @@
             * [TernarySearch](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/TernarySearch.java)
             * [UnionFind](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/UnionFind.java)
             * [UpperBound](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/UpperBound.java)
+          * slidingwindow
+            * [MaxSumKSizeSubarray](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarray.java)
           * sorts
             * [AdaptiveMergeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/AdaptiveMergeSort.java)
             * [BeadSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/BeadSort.java)
@@ -826,6 +830,7 @@
               * [HashMapCuckooHashingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/hashmap/HashMapCuckooHashingTest.java)
             * heaps
               * [FibonacciHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/FibonacciHeapTest.java)
+              * [GenericHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/GenericHeapTest.java)
               * [LeftistHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java)
             * lists
               * [CircleLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CircleLinkedListTest.java)
@@ -942,6 +947,7 @@
             * [BinaryAdditionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/BinaryAdditionTest.java)
             * [CoinChangeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/CoinChangeTest.java)
             * [DigitSeparationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/DigitSeparationTest.java)
+            * [EgyptianFractionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/EgyptianFractionTest.java)
             * [FractionalKnapsackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/FractionalKnapsackTest.java)
             * [GaleShapleyTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/GaleShapleyTest.java)
             * [JobSequencingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/JobSequencingTest.java)
@@ -969,6 +975,7 @@
             * [BinaryPowTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/BinaryPowTest.java)
             * [BinomialCoefficientTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/BinomialCoefficientTest.java)
             * [CeilTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/CeilTest.java)
+            * [ChineseRemainderTheoremTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/ChineseRemainderTheoremTest.java)
             * [CollatzConjectureTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/CollatzConjectureTest.java)
             * [CombinationsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/CombinationsTest.java)
             * [ConvolutionFFTTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/ConvolutionFFTTest.java)
@@ -1155,6 +1162,8 @@
             * [TestSearchInARowAndColWiseSortedMatrix](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/TestSearchInARowAndColWiseSortedMatrix.java)
             * [UnionFindTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/UnionFindTest.java)
             * [UpperBoundTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/UpperBoundTest.java)
+          * slidingwindow
+            * [MaxSumKSizeSubarrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarrayTest.java)
           * sorts
             * [AdaptiveMergeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/AdaptiveMergeSortTest.java)
             * [BeadSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/BeadSortTest.java)
diff --git a/src/main/java/com/thealgorithms/greedyalgorithms/EgyptianFraction.java b/src/main/java/com/thealgorithms/greedyalgorithms/EgyptianFraction.java
new file mode 100644
index 00000000..35cbfe87
--- /dev/null
+++ b/src/main/java/com/thealgorithms/greedyalgorithms/EgyptianFraction.java
@@ -0,0 +1,35 @@
+package com.thealgorithms.greedyalgorithms;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Class to represent a fraction as a sum of unique unit fractions.
+ * Example:
+ * 2/3 = 1/2 + 1/6
+ * 3/10 = 1/4 + 1/20
+ *
+ * @author Hardvan
+ */
+public final class EgyptianFraction {
+    private EgyptianFraction() {
+    }
+
+    /**
+     * Calculates the Egyptian Fraction representation of a given fraction.
+     *
+     * @param numerator   the numerator of the fraction
+     * @param denominator the denominator of the fraction
+     * @return List of unit fractions represented as strings "1/x"
+     */
+    public static List<String> getEgyptianFraction(int numerator, int denominator) {
+        List<String> result = new ArrayList<>();
+        while (numerator != 0) {
+            int x = (int) Math.ceil((double) denominator / numerator);
+            result.add("1/" + x);
+            numerator = numerator * x - denominator;
+            denominator = denominator * x;
+        }
+        return result;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/greedyalgorithms/EgyptianFractionTest.java b/src/test/java/com/thealgorithms/greedyalgorithms/EgyptianFractionTest.java
new file mode 100644
index 00000000..1d34876d
--- /dev/null
+++ b/src/test/java/com/thealgorithms/greedyalgorithms/EgyptianFractionTest.java
@@ -0,0 +1,22 @@
+package com.thealgorithms.greedyalgorithms;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.List;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class EgyptianFractionTest {
+
+    @ParameterizedTest
+    @MethodSource("fractionProvider")
+    public void testGetEgyptianFraction(int numerator, int denominator, List<String> expected) {
+        assertEquals(expected, EgyptianFraction.getEgyptianFraction(numerator, denominator));
+    }
+
+    private static Stream<Arguments> fractionProvider() {
+        return Stream.of(Arguments.of(2, 3, List.of("1/2", "1/6")), Arguments.of(3, 10, List.of("1/4", "1/20")), Arguments.of(1, 3, List.of("1/3")), Arguments.of(1, 2, List.of("1/2")), Arguments.of(4, 13, List.of("1/4", "1/18", "1/468")));
+    }
+}