We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I would like to give kudos to the Hackerrank team for normally doing a good job of extending Project Euler questions and checking for computational complexity but this is not your best work here. I really think you should remove most of the test cases and let this problem be "easy".
"We never cancel any 0." To remove trailing 0's would be a trivial example. This makes sense to a mathematician because "trivial" here means that it doesn't take any effort to construct or check these examples and that the real interest of the problem occurs when we ignore those examples. That said, 4808/8414=8/14 is NOT trivial and should be considered an example. This would be in line with normal definition of "trivial" AND the problem statement.
You should make it clearer that we don't count fractions twice if they cancel two different ways, e.g. 1616/6464 cancels to either 161/644 or 116/464 but we count 1616/6464 just once. The instructions make is seem like the full equality "49/98=4/8" is an example but only "49/98" is.
You should also make it clearer that if we cancel and have leading zeros then that is an example, e.g. 3016/6032 = 01/02 is an example. Here we have "01" is NOT a two digit number before a cancelation but IS a two digit number after a cancalation.
That said, this is actually a very interesting problem that doesn't succumb to an easy solution.
After a lot of work it reduces to a Diophantine equation... hmmmm.... This doesn't bode well for figuring out the cases with 3+ digits.
After a lot of work I figured out something much better than brute force:
Consider that we want solutions "n/d = n2/d2". Iterate through possible values of n which has N digits. Then iterate over N-K possible digits from the digits of n (N choose N-K) to make n2. Now, consider n/n2. We must have n/n2 = d/d2 and d must have the digit/s of n that n2 doesn't have. The clever step is to iterate through fractions that are equal to n/n2; this means divide both n and n2 by g = gcd(n, n2) and then multiply both n/g and n2 /g by integer i, which you will iterate. If we write n/n2 as an ordered pair (n, n2) then the iteration looks like ((n/g)*i, (n2/g)*i), i++, and for each iteration of i you check if (n/g)*i has the digits of n that n2 doesn't have.
If this problem feels too complex then a great way to break it up is to consider the 6 different test cases seperately. That is what I did to come up with fast solutions.
I haven't checked the time complexity of my solution but by using this method I got all of my Python solutions to execute in under 2 seconds. I used Python's math.gcd function which is implemented in C and I'm not sure if that is what made my code run fast perhaps without good time complexity. I'm too fed up with this problem right now to think about it any more.
Overall I felt like I was programming something arbitrary and needed to code it the exact way the Hackerrank team had in mind to get full credit.
Project Euler #33: Digit canceling fractions
You are viewing a single comment's thread. Return to all comments →
I would like to give kudos to the Hackerrank team for normally doing a good job of extending Project Euler questions and checking for computational complexity but this is not your best work here. I really think you should remove most of the test cases and let this problem be "easy".
"We never cancel any 0." To remove trailing 0's would be a trivial example. This makes sense to a mathematician because "trivial" here means that it doesn't take any effort to construct or check these examples and that the real interest of the problem occurs when we ignore those examples. That said, 4808/8414=8/14 is NOT trivial and should be considered an example. This would be in line with normal definition of "trivial" AND the problem statement.
You should make it clearer that we don't count fractions twice if they cancel two different ways, e.g. 1616/6464 cancels to either 161/644 or 116/464 but we count 1616/6464 just once. The instructions make is seem like the full equality "49/98=4/8" is an example but only "49/98" is.
You should also make it clearer that if we cancel and have leading zeros then that is an example, e.g. 3016/6032 = 01/02 is an example. Here we have "01" is NOT a two digit number before a cancelation but IS a two digit number after a cancalation.
That said, this is actually a very interesting problem that doesn't succumb to an easy solution.
The two digit case is worked out here: https://www.mathblog.dk/project-euler-33-fractions-unorthodox-cancelling-method/
After a lot of work it reduces to a Diophantine equation... hmmmm.... This doesn't bode well for figuring out the cases with 3+ digits.
After a lot of work I figured out something much better than brute force:
Consider that we want solutions "n/d = n2/d2". Iterate through possible values of n which has N digits. Then iterate over N-K possible digits from the digits of n (N choose N-K) to make n2. Now, consider n/n2. We must have n/n2 = d/d2 and d must have the digit/s of n that n2 doesn't have. The clever step is to iterate through fractions that are equal to n/n2; this means divide both n and n2 by g = gcd(n, n2) and then multiply both n/g and n2 /g by integer i, which you will iterate. If we write n/n2 as an ordered pair (n, n2) then the iteration looks like ((n/g)*i, (n2/g)*i), i++, and for each iteration of i you check if (n/g)*i has the digits of n that n2 doesn't have.
If this problem feels too complex then a great way to break it up is to consider the 6 different test cases seperately. That is what I did to come up with fast solutions.
I haven't checked the time complexity of my solution but by using this method I got all of my Python solutions to execute in under 2 seconds. I used Python's math.gcd function which is implemented in C and I'm not sure if that is what made my code run fast perhaps without good time complexity. I'm too fed up with this problem right now to think about it any more.
Overall I felt like I was programming something arbitrary and needed to code it the exact way the Hackerrank team had in mind to get full credit.
Feel free to message me for test case data.