Simplifying … wrong?
Project Euler 33
Read it in italian on n-bit.it
Welcome back with another problem to solve! Today we are dealing with some math, simplifying some already simple fractions. But we’ll doing it wrong and, with some help from the fate, we’ll get out with it!
Today’s problem is proposed by ProjectEuler.net, a fantastic website where you can find more than 800 math and coding problems to tackle and solve. Go take a look at it: rest assured it will definitely be worth it!
Also, I’d like to anticipate one thing: as for all the other problems proposed by PE.net, we’ll reason about the problem and we’ll see an algorithm to solve it. You won’t find the direct solution to it though: PE.net is so committed to teach and to have people trying to tackle their problems by themselves, that publishing solutions for their problems is actually prohibited. This is one of the first 100 problems, though, for which this rule does not apply. Nevertheless, I don’t think it would be correct to just throw away the solution like that. So have a go and have fun!
The problem
Let’s jump to the problem then!
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, 30/50 = 3/5 , to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.
The problem shows that simplifying the fraction 49/98 in a wrong way, just cutting away the 9s, we obtain an actual correct solution, namely 4/8 = 1/2. We are told that the fractions which have this kind of behavior are exactly four, with their value between 0 and 1: our job is to find those four fractions and, to demonstrate we actually did it.
Even if the problem is not the most complex ever, there are some key ideas which will help us a lot while trying to solve the problem. Let’s think about it.
The idea
First things first: the problem points out that both the numerator and the denominator must be 2-digit integers. This implies that, if n id the numerator and d is the denominator, then we’ll have that 10 ≤ n,d ≤ 99. If we think about it a little more, though, it comes natural that it will be impossible for a n=10 to not give a trivial solution:
- if we “simplify” the 1 from the 10, we’ll be left with 0 as numerator, which will give us 0 as a result in every case;
- if we “simplify” the 0, instead, that would mean we are facing a trival fraction, like 10/20, 10/30 and so on.
So, our new range of possible integers will become 10 < n ≤ 99 and 10 ≤ d ≤ 99.
Second, the problem states that the result r of the fraction must be 0 < r < 1 : this means that it’s impossible for the numerator to be greater than the denominator. It’s quite simple to prove: let’s suppose that n is greater than d by an integer k. Then (n+k)/d = n/d + k/d = 1 + k/d > 1. This means that our n must always be lesser than d. We can rewrite the ranges of our possibilities then: 10 < n < 98 and 11 < d < 99.
Get Nicola Moro’s stories in your inbox
Join Medium for free to get updates from this writer.
Finally, we’ll also need to calculate the correct value for each possible fraction we’ll compose, to verify that its “simplified” version matches. This means that we’ll be somehow brute-forcing the solution, calculating each possible value. In short, our algorithm will do something like this:
Let’s see the algorithm then!
The code
Ok, let’s take a look. First off, we create a variable num, which will keep track of the value of the numerator at each loop, and a variable collector in which we’ll store the results we find.
Now we start with the loops: we first create an external loop, which will be executed until num > 10 : as we said, we can’t go below 11 with the numerator. Inside this first loop we create a variable denom which will hold the current value of the denominator. Then we start the inner loop and we run it until the denominator is greater than the numerator (note that if num = denom then num/denom = 1 and we don’t need it).
We get instantly rid of the trivial fractions: if that’s the case, we lower the denom by one and continue.
If it’s not trivial, we calculate the actualResult of the fraction and we decompose both the numerator and denominator in two lists of digits and filter those lists, such that common digits between the two are not considered. We store unique digits in two other lists, newNumDigits and newDenomDigits . Also, we verify that none of them is empty: if one of them is, that means we removed both digits from each and we are left with nothing to compare. In this case we simply lower the denum again by one and continue.
If they’re not empty, we “recompose” the new “simplified” numerator and denominator ( newNumerator = int("".join(newNumDigits)) e newDenominator = int("".join(newDenomDigits)) ). If one of them is equal to the starting num or denom that means we simplified nothing, like in the case of 23/45, for example. This cannot be one of the fractions we are looking for, so we move on. Also, we check if the new denominator is not 0, so to avoid a division error.
Then we simply check if the fraction made up by our new simplified terms is equal to the original fraction : if newNumerator/newDenominator == actualResult . If it is, we found a result and we add it to the collector. We can also print out a string to inform that the algorithm found a solution.
Finally, we print out the collector.
Now to get the actual solution, you just need to multiply those four fractions and simplify everything (correctly, this time! 😅).
Time complexity
As usual, let’s spend a moment talking about the complexity of the algorithm. First off, we notice that most of the time spent by the routine is the one inside the for loops. These are nested loops, meaning that for each iteration of the outer loop we’re going to execute every possible iteration of the inner loop, until the condition denom > num remains valid. Even if the number of possible fractions to consider is constant (we go at most from 99 to 11), let’s generalize the concept and consider that if we run the outer loop n times and for each of those we run the inner loop n times, we’re stuck with O(n²) time complexity.
This is not really precise though: in fact, for higher values of num we execute the inner loop less times. If num=98 , for example, we only need to consider 98/99 . Then num=97 and we’ll only need to consider 97/99 and 97/98 , and so on. If we try to draw this kind of approach on a table we get something like this:
Each of the xs above shows a fraction we need to consider, so we are considering only half of all the possible permutations of the numerators and denominators. This will lead us to a time complexity of O(n²/2), but since we must not consider multiplicative constant while analyzing the complexity we must get rid of the 1/2 and consider only O(n²).
Conclusions
These fractions are strange, aren’t they? Nevertheless, another problems bites the dust!
I hope you found the article interesting enough to read it up to here and I also hope it left you with something valuable to reason about. If so, please consider leaving a clap or two and share the article to a friend who could find it interesting: that would make my day and it would be a great help to keep the blog going!
As always, a huge thanks for reading,
Nicola
