# Project Euler #33: Digit canceling fractions

# Project Euler #33: Digit canceling fractions

JialinOuyang + 2 comments When the author made such big changes to the original problem, I think adding some notes to tell users would be better.

On the other hand, the description of the new problem almost tells nothing about the key restrictions. And leave it as a black box to let users guess and discuss.

1) The digits removed from the numerator and the denominator should be the same and could be in any order. For example, 6483/8644=3/4 where the numerator canceled {6,4,8} and the denominator canceled {8,6,4};

2) Leading zeros are allowed in the post-cancled number. For instance, 4808/8414=8/14 is a valid fraction for N=4 and K=2.

tkokan + 0 comments Thanks for this explanation. And I agree, those should be written in the problem itself.

childeroland + 1 comment Many thanks to JialinOuyang, this helped a lot! Here are some additions:

2a) It is OK for leading zeros to be in both the numerator and the denominator of the "cancelled" fraction. e.g. 3016/6032 = 01/02

3) Trailing zeros are not banned, you just mustn't "cancel" them, so 490/980 = 40/80 is OK, but 490/980 = 4/8 is not.

4) Each fraction should only be counted once, even if it can be validly "cancelled" in more than one way, e.g. 1616/6464 cancels to either 161/644 or 116/464, but it only counts once.

5) Fractions don't have to be completely "cancelled", so 1616/6464 = 161/644 is OK even though there are still 6's in both "cancelled" numbers.

I didn't solve this one until I had tried all of the above both ways - I strongly agree the problem statement should be clearer about the rules.

FOREVER_MAPLE + 0 comments I spend several hours understanding this description. For N=4, K=3. 1306/6530 = 1/5 is not ok. It's not a trivial example. But it cancels zero.

SalvadorDali + 1 comment `Which means fractions where trailing 0's are cancelled are trivial. So we will ignore all the cases where we have to cancel 0's.`

How these two sentences are connected? It is similar to "the cat can eat a mouse. So let's not count elephants in the room".

If we are planning to ignore all the cancellation of 0, why do we need to write something about trailing zeros and trivial fractions?

mdev + 0 comments Dude you are so right. I just wasted my 3 hrs because of the stupid description. I said 'stupid' because the above comment was written a year ago, and still no attempt to revise it. Huh!!!!

nothlione + 0 comments I'm glad I came to Discussions before trying to implement, this time. Thought the question was too ambiguous and it is even more ambiguous than I thought.

The description is terribly stated, lots of people have already pointed out mistakes in it and @shashank21j does absolutely nothing to fix it. Come on, it's been 2 years already.

hagman + 4 comments Is canceling the zero as on 204/102 = 24/12 also called trivial? What about cancelling the non-terminal zero in 100/200=10/20

shashank21jHackerRank AdminChallenge Author + 1 comment We never cancel any 0.

mdev + 0 comments WILL YOU PLEASE ADD THIS TO DESCRPTION ... NEVEEERRRRR CANNNCELLL 0 to 0 .. BE IT TRAILING MIDDLE FRONT anywhere ....

wyllian + 0 comments So, if we have N = 4 and K = 1. Is the number 1908/8904 = 108/804 valid? Note that I'm not "cancelling" number zero and there's no trailing zeros in the original fraction.

wyllian + 0 comments Sorry, my example was very bad. And the answer is not valid. However, I'd like to know if this kind of cancelation is possible. That is, can I "cancel" a digit (different of zero) even when I have zeros (not trailing) in both denominator and numerator?

shashank21jHackerRank AdminChallenge Author + 0 comments @wyllian Yes. you can cancel anything other than 0

yury_dymov + 2 comments Answers for n = 3, k = 1: 77262 163829 n = 3, k = 2: 7429 17305

This should help to reverse engeneer the initial task :)

mike006322 + 0 comments To help with the testing data, here are the corresponding fractions for n = 3, k = 1:

(253, 451, 23, 41) (297, 495, 27, 45) (398, 597, 38, 57) (390, 975, 30, 75) (496, 992, 46, 92) (199, 796, 19, 76) (693, 990, 63, 90) (187, 781, 17, 71) (891, 990, 81, 90) (395, 790, 35, 70) (396, 792, 36, 72) (597, 995, 57, 95) (396, 495, 36, 45) (392, 980, 32, 80) (583, 781, 53, 71) (493, 986, 43, 86) (596, 894, 56, 84) (216, 864, 21, 84) (594, 792, 54, 72) (495, 792, 45, 72) (191, 955, 11, 55) (286, 583, 26, 53) (270, 756, 20, 56) (462, 660, 42, 60) (268, 469, 28, 49) (136, 340, 16, 40) (796, 995, 76, 95) (149, 894, 14, 84) (297, 891, 27, 81) (156, 858, 16, 88) (176, 770, 16, 70) (242, 341, 22, 31) (168, 672, 18, 72) (198, 594, 18, 54) (363, 660, 33, 60) (176, 275, 16, 25) (136, 238, 16, 28) (396, 891, 36, 81) (199, 995, 19, 95) (286, 385, 26, 35) (451, 550, 41, 50) (299, 897, 29, 87) (335, 737, 35, 77) (473, 572, 43, 52) (299, 598, 29, 58) (394, 985, 34, 85) (597, 796, 57, 76) (352, 451, 32, 41) (134, 938, 14, 98) (194, 970, 14, 70) (160, 640, 10, 40) (671, 770, 61, 70) (266, 665, 26, 65) (163, 652, 13, 52) (149, 596, 14, 56) (217, 775, 21, 75) (385, 583, 35, 53) (427, 976, 42, 96) (536, 938, 56, 98) (132, 231, 12, 21) (187, 385, 17, 35) (154, 550, 14, 50) (346, 865, 34, 85) (594, 990, 54, 90) (275, 671, 25, 61) (187, 484, 17, 44) (490, 980, 40, 80) (234, 936, 24, 96) (682, 781, 62, 71) (394, 591, 34, 51) (536, 737, 56, 77) (187, 880, 17, 80) (374, 473, 34, 43) (781, 880, 71, 80) (196, 294, 16, 24) (385, 484, 35, 44) (298, 596, 28, 56) (737, 938, 77, 98) (335, 938, 35, 98) (305, 854, 30, 84) (164, 656, 14, 56) (154, 451, 14, 41) (198, 891, 18, 81) (154, 253, 14, 23) (143, 242, 13, 22) (199, 597, 19, 57) (385, 781, 35, 71) (196, 980, 16, 80) (286, 682, 26, 62) (249, 498, 24, 48) (186, 465, 18, 45) (253, 352, 23, 32) (169, 676, 19, 76) (199, 398, 19, 38) (195, 975, 15, 75) (176, 671, 16, 61) (264, 660, 24, 60) (297, 693, 27, 63) (572, 671, 52, 61) (138, 345, 18, 45) (165, 660, 15, 60) (491, 982, 41, 82) (176, 473, 16, 43) (396, 693, 36, 63) (165, 363, 15, 33) (484, 781, 44, 71) (133, 532, 13, 52) (196, 490, 16, 40) (385, 880, 35, 80) (693, 792, 63, 72) (197, 591, 17, 51) (286, 880, 26, 80) (341, 440, 31, 40) (286, 781, 26, 71) (178, 979, 18, 99) (143, 440, 13, 40) (484, 682, 44, 62) (396, 594, 36, 54) (167, 668, 17, 68) (363, 462, 33, 42) (298, 894, 28, 84) (275, 473, 25, 43) (594, 693, 54, 63) (119, 595, 11, 55) (193, 965, 13, 65) (275, 572, 25, 52) (112, 616, 12, 66) (146, 365, 14, 35) (161, 644, 11, 44) (187, 286, 17, 26) (198, 396, 18, 36) (291, 970, 21, 70) (392, 490, 32, 40) (363, 561, 33, 51) (792, 990, 72, 90) (198, 990, 18, 90) (162, 648, 12, 48) (268, 670, 28, 70) (294, 490, 24, 40) (233, 932, 23, 92) (397, 794, 37, 74) (296, 592, 26, 52) (198, 495, 18, 45) (132, 330, 12, 30) (398, 995, 38, 95) (399, 798, 39, 78) (498, 996, 48, 96) (561, 660, 51, 60) (275, 374, 25, 34) (134, 737, 14, 77) (176, 374, 16, 34) (374, 770, 34, 70) (494, 988, 44, 88) (196, 392, 16, 32) (198, 297, 18, 27) (462, 561, 42, 51) (572, 770, 52, 70) (396, 990, 36, 90) (306, 765, 30, 75) (121, 220, 11, 20) (260, 650, 20, 50) (335, 536, 35, 56) (197, 394, 17, 34) (134, 335, 14, 35) (165, 264, 15, 24) (192, 960, 12, 60) (165, 561, 15, 51) (473, 770, 43, 70) (190, 950, 10, 50) (264, 462, 24, 42) (469, 670, 49, 70) (106, 265, 10, 25) (183, 732, 18, 72) (224, 728, 24, 78) (386, 965, 38, 95) (187, 682, 17, 62) (374, 671, 34, 61) (176, 572, 16, 52) (116, 464, 11, 44) (143, 341, 13, 31) (495, 891, 45, 81) (130, 325, 10, 25) (495, 990, 45, 90) (594, 891, 54, 81) (352, 550, 32, 50) (139, 695, 13, 65) (297, 990, 27, 90) (499, 998, 49, 98) (332, 830, 32, 80) (484, 880, 44, 80) (591, 985, 51, 85) (473, 671, 43, 61) (693, 891, 63, 81) (264, 561, 24, 51) (179, 895, 17, 85) (275, 770, 25, 70) (295, 590, 25, 50) (286, 484, 26, 44) (598, 897, 58, 87) (792, 891, 72, 81) (583, 682, 53, 62) (134, 536, 14, 56) (149, 298, 14, 28) (385, 682, 35, 62) (226, 565, 22, 55) (532, 931, 52, 91) (166, 664, 16, 64) (297, 792, 27, 72) (349, 698, 34, 68) (195, 390, 15, 30) (242, 440, 22, 40) (294, 392, 24, 32) (194, 291, 14, 21) (297, 396, 27, 36) (197, 985, 17, 85) (484, 583, 44, 53) (264, 363, 24, 33) (159, 795, 15, 75) (262, 655, 22, 55) (497, 994, 47, 94) (249, 996, 24, 96) (198, 792, 18, 72) (253, 550, 23, 50) (449, 898, 44, 88) (583, 880, 53, 80) (198, 693, 18, 63) (231, 330, 21, 30) (297, 594, 27, 54) (495, 594, 45, 54) (294, 980, 24, 80) (133, 931, 13, 91) (238, 340, 28, 40) (398, 796, 38, 76) (165, 462, 15, 42) (334, 835, 34, 85) (492, 984, 42, 84) (374, 572, 34, 52) (682, 880, 62, 80) (154, 352, 14, 32) (495, 693, 45, 63) (187, 583, 17, 53)

NotAnAmbiTurner + 0 comments Thank you! I've never understood why some questions have (1) bad descriptions coupled with (2) few test cases. Makes it soooo difficult.

mike006322 + 0 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.

stbrumme + 1 comment The problem is called "Anomalous Cancellation". A bit more information can be found here: http://mathworld.wolfram.com/AnomalousCancellation.html

jeekobu + 0 comments In anomalous cancellation (as discussed in the link), you can cancel 0s, so long as they aren't trailing. (1019/5095 == 11/55 is an example.) So it's not quite the same.

In the article, trailing 0s are not allowed... but this isn't stated, just implied by the examples. In other words, the article is almost as vague as this challenge. Truly a "figure out wtf the author is thinking" situation.

cantonios + 2 comments Any hints on making this faster? My current c++ implementation takes about 4s for N=4, K=2. It's essentially: (1) brute-forcing every numerator/denominator, (2) checking the number of common digits to see if we could actually try to cancel at least k, (3) if so, try all possible ways of cancelling k digits

I can cheat, precompute the 6 possibilities and have a look-up table. But just wondering if there's a mathematical trick to make this problem easier.

jpulgarin + 0 comments I'm doing the same approach as you. Haven't found a more elegant algorithm :(

zo0ok + 0 comments I did the same thing and used a Union with uint32_t raw; uint8_t digits[4];

That way I can use raw for assignment and comparison. Then I have overloaded things like ++.

This way I never need to use division to figure out the digits of a number.

It is still not fast enought for all of them.

mike006322 + 0 comments To help with testing, for N = 2, K = 1 we have the following fractions which satisfiy the conditions: 16/64 = 1/4, 19/95 = 1/5, 26/65 = 2/5, 49/98 = 4/8. Sum of numerators on the left of the equalities = 110, sum of denominators = 322.

cakulev + 1 comment My test case #4 is failing, rest is good. Not sure for case N=4 , K = 2. For example 1224/2142 = 12/21 ( remove 2 and 4), but also 1224/2142 = 24/42 ( remove 1 and 2). Do we include above twice or only once?

tony_hager + 0 comments Once

Sort 28 Discussions, By:

Please Login in order to post a comment