# 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.

Sort 28 Discussions, By:

Please Login in order to post a comment