## DEV Community is a community of 880,569 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Divide pizzas with a Greedy approach & Python

Consider that you are having 10 friends over and have ordered 7 pizzas. How can you divide those pizzas fairly? One way is for everyone to get half a pizza and a fifth of a pizza. (for example, by splitting 2 pizzas in fifths and the other 5 in halves).

If we were to represent our problem as fractions: This way of writing a fraction as a sum of distinct unit fractions (fractions that have a numerator equal to 1 and the denominator a positive integer) was used as a serious notation for the rational numbers by ancient Egyptians and is called an Egyptian fraction.

We can use the computer to find the Egyptian notation for any fraction using a fairly simple greedy approach: in short, for any given fraction M/N, find the least integer greater than or equal to N/M, let it be x, and then recur for M/N - 1/x until the result is 0.

Alright, let's code a solution! Firstly, we have to read our M and N. Let's make the user give it as M/N:

``````M, N = [int(x) for x in input("M/N = ").split('/')]
``````

Now, let's write a function that prints the sum:

``````def egyptian_fraction(m, n):
while m > 0: # we recur until m is 0
x = n // m
if n % m != 0: # if n is not divisible by m, we have to add 1 in order to respect the 'greater than or equal' part.
x += 1
m = m * x - n # when calculating, M/N - 1/x = (M*x - N) / N
n *= x
print("1/{0}".format(x), " + " if m != 0 else "", sep = "") # print the numbers like: 1/2 + 1/5
``````

In the end, our program could look like this:

``````def egyptian_fraction(m, n):
while m > 0:
x = n // m
if n % m != 0:
x += 1
m = m * x - n
n *= x
print("1/{0}".format(x), " + " if m != 0 else "", sep = "")

M, N = [int(x) for x in input("M/N = ").split('/')]
egyptian_fraction(M, N)
``````

So, in the end, we have a program capable of dividing pizzas equally among our guests! As a matter of fact, this approach can be used to divide any object in equal shares.