Egyptian Fraction Problem
Ancient Egyptians represented each positive fraction as the sum of unique unit fractions. For example, 7/15 = 1/3 + 1/8 + 1/120
, or 2/3 = 1/2 + 1/6
, or 1/7 = 1/7
.
So, your goal is to find such a representation for the number n/m
, m, n>0.
That can be reached by using the Greedy Approach. Each time, try to βbiteβ the number as big as possible to reduce the current value. Letβs look at the 7/15
:
-
N = 7/15 >= 1/3 β this is the maximum unit fraction we can reach, add it to the answer.
-
Now, update the number weβre solving problem for: N = 7/15 β 1/3 = 2/15.
-
N = 2/15 >= 1/8 β next maximum unit fraction, add to the answer.
-
Update N: N = 2/15 β 1/8 = 1/120.
-
N = 1/120 >= 1/120 - add to the answer.
-
Update N = 0 -> stop the algorithm.
So, to sum up:
-
Check if the current N == 0. If it is, stop the algorithm.
-
Find the biggest unit fraction less than N and add it to the ans
-
Update value of N by reducing.
The answer is an array f
of numbers f[0], f[1], ... , f[t]
, where f[i]
is a divider for fraction 1/f[i]
. For our example, answer is [3, 8, 120]
.
How to find the biggest possible unit fraction It can be easily done for
N = n/m
by calculatingk = math.ceil(m/n)
. Greater values ofk
do not give the maximum unit fraction (since, for example,1/k > 1/(k+1)
).
Swipe to start coding
Add some code to the function and test it.
Thanks for your feedback!
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Summarize this chapter
Explain the code in file
Explain why file doesn't solve the task
Awesome!
Completion rate improved to 7.69
Egyptian Fraction Problem
Swipe to show menu
Ancient Egyptians represented each positive fraction as the sum of unique unit fractions. For example, 7/15 = 1/3 + 1/8 + 1/120
, or 2/3 = 1/2 + 1/6
, or 1/7 = 1/7
.
So, your goal is to find such a representation for the number n/m
, m, n>0.
That can be reached by using the Greedy Approach. Each time, try to βbiteβ the number as big as possible to reduce the current value. Letβs look at the 7/15
:
-
N = 7/15 >= 1/3 β this is the maximum unit fraction we can reach, add it to the answer.
-
Now, update the number weβre solving problem for: N = 7/15 β 1/3 = 2/15.
-
N = 2/15 >= 1/8 β next maximum unit fraction, add to the answer.
-
Update N: N = 2/15 β 1/8 = 1/120.
-
N = 1/120 >= 1/120 - add to the answer.
-
Update N = 0 -> stop the algorithm.
So, to sum up:
-
Check if the current N == 0. If it is, stop the algorithm.
-
Find the biggest unit fraction less than N and add it to the ans
-
Update value of N by reducing.
The answer is an array f
of numbers f[0], f[1], ... , f[t]
, where f[i]
is a divider for fraction 1/f[i]
. For our example, answer is [3, 8, 120]
.
How to find the biggest possible unit fraction It can be easily done for
N = n/m
by calculatingk = math.ceil(m/n)
. Greater values ofk
do not give the maximum unit fraction (since, for example,1/k > 1/(k+1)
).
Swipe to start coding
Add some code to the function and test it.
Thanks for your feedback!
Awesome!
Completion rate improved to 7.69single