Problem Statement
A rational number is a number which can be expressed as a ratio of two integers. In addition, all rational numbers can be expressed as a decimal number with some repeating periodic part (in some cases the repeating part is 0). For example 1/7 = 0.1428571428571428... with 142857 repeating itself infinitely. Other fractions have some finite number of non-repeating digits before the periodic part begins. For example, 1/6 = 0.166666... starts with a 1 and then settles into repeating 6's.
Your task is to write a class Decimal with a method find that takes four int's: lower, upper, lowerLength, and upperLength. Your method must find all integers n between lower and upper, inclusive, where the repeating portion of the decimal representation of 1/n has between lowerLength and upperLength digits, inclusive. You should return all of the numbers you find in a
Definition
- Class:
- Decimal
- Method:
- find
- Parameters:
- int, int, int, int
- Returns:
- int[]
- Method signature:
- int[] find(int lower, int upper, int lowerLength, int upperLength)
- (be sure your method is public)
Constraints
- lower and upper will be between 1 and 1000000, inclusive.
- upper will be greater than or equal to lower.
- The difference between upper and lower will be at most 100.
- lowerLength and upperLength will be between 1 to 1000000, inclusive.
- upperLength will be greater than or equal to lowerLength.
Examples
1
10
1
1
Returns: { 1, 2, 3, 4, 5, 6, 8, 9, 10 }
1/1 = 1.00000... 1/2 = 0.50000... 1/3 = 0.33333... 1/4 = 0.25000... 1/5 = 0.20000... 1/6 = 0.16666... 1/8 = 0.12500... 1/9 = 0.11111... 1/10 = 0.10000... Thus, all of the numbers other than 7 eventually settle into a repeating sequence of exactly 1 digit.
999899
999999
1
1000
Returns: { 999900, 999908, 999936, 999950, 999954, 999960, 999975, 999980, 999990, 999996, 999999 }
888899
888999
100000
1000000
Returns: { 888909, 888911, 888917, 888919, 888922, 888923, 888926, 888931, 888938, 888941, 888946, 888947, 888961, 888967, 888971, 888973, 888974, 888977, 888981, 888982, 888983, 888988, 888989, 888997 }
55
56
1
10
Returns: { 55, 56 }
1/55 = 0.01818... (18 is repeating) 1/56 = 0.017857142857142... (857142 is repeating) Both of these numbers have between 1 and 10 digits in its repeating part.
200
300
10
20
Returns: { 204, 209, 212, 228, 237, 247, 248, 255, 265, 266, 272, 279, 285 }
999900
1000000
1
1000000
Returns: { 999900, 999901, 999902, 999903, 999904, 999905, 999906, 999907, 999908, 999909, 999910, 999911, 999912, 999913, 999914, 999915, 999916, 999917, 999918, 999919, 999920, 999921, 999922, 999923, 999924, 999925, 999926, 999927, 999928, 999929, 999930, 999931, 999932, 999933, 999934, 999935, 999936, 999937, 999938, 999939, 999940, 999941, 999942, 999943, 999944, 999945, 999946, 999947, 999948, 999949, 999950, 999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964, 999965, 999966, 999967, 999968, 999969, 999970, 999971, 999972, 999973, 999974, 999975, 999976, 999977, 999978, 999979, 999980, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999990, 999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998, 999999, 1000000 }
1
100
50
100
Returns: { 59, 61, 97 }
999983
999983
999982
999982
Returns: { 999983 }
The repeating part of 1/999983 is 999982 digits long!
355119
355143
90784
368025
Returns: { 355127, 355139 }
868392
868476
219366
683093
Returns: { 868397, 868407, 868409, 868423, 868429, 868433, 868453, 868469 }
727670
727707
603744
800952
Returns: { 727691, 727703 }
837000
837095
210893
606638
Returns: { 837021, 837043, 837061, 837069, 837071, 837079, 837087 }
683599
683672
581225
883633
Returns: { 683651 }
966316
966337
76495
322779
Returns: { 966319, 966324, 966326, 966327, 966332, 966333 }
469396
469431
83166
609936
Returns: { 469397, 469412, 469423, 469426, 469427, 469429 }
801373
801426
364541
680463
Returns: { 801377, 801401, 801406 }
598185
598197
99668
784043
Returns: { 598187, 598189, 598193 }
782137
782227
17001
104484
Returns: { 782138, 782140, 782143, 782148, 782152, 782153, 782156, 782159, 782163, 782165, 782168, 782170, 782172, 782178, 782181, 782182, 782185, 782186, 782198, 782201, 782204, 782205, 782211, 782212, 782214, 782215, 782216, 782222, 782224, 782226, 782227 }
297227
297319
99309
616876
Returns: { 297227, 297229, 297233, 297239, 297247, 297257, 297263, 297269, 297293, 297301, 297311 }
440360
440455
75030
638159
Returns: { 440369, 440371, 440378, 440383, 440386, 440389, 440393, 440417, 440421, 440423, 440434, 440437, 440441, 440443, 440446 }
896690
896782
318527
752287
Returns: { 896693, 896699, 896713, 896717, 896723, 896734, 896741, 896758 }
974636
974670
131030
424174
Returns: { 974643, 974653 }
602395
602432
109277
413605
Returns: { 602401, 602417, 602421, 602423, 602428, 602431 }
925138
925146
66882
488074
Returns: { 925138, 925139, 925141, 925142 }
948942
949022
471764
707236
Returns: { 948947, 948982, 948994, 949001, 949006 }
623694
623747
45674
105277
Returns: { 623698, 623701, 623703, 623706, 623724, 623726, 623731, 623741, 623747 }
383709
383764
165104
490663
Returns: { 383722, 383723, 383753, 383759 }
369651
369734
246621
699847
Returns: { 369659, 369661, 369673, 369731 }
224555
224617
55159
447061
Returns: { 224567, 224569, 224571, 224573, 224578, 224579, 224582, 224591, 224593, 224596, 224603, 224606, 224607, 224611, 224617 }
755381
755385
58460
277935
Returns: { 755382, 755383 }
962774
962843
184164
320664
Returns: { 962774, 962794, 962801, 962804, 962813 }
666452
666512
578171
856928
Returns: { 666461 }
619730
619773
495190
997175
Returns: { 619739, 619771 }
447724
447760
335593
940328
Returns: { 447743, 447749 }
986079
986133
64225
140789
Returns: { 986082, 986092, 986107, 986111, 986122 }
977382
977440
890482
981531
Returns: { 977407 }
550800
550822
114389
241970
Returns: { 550801, 550822 }
531327
531407
218023
291443
Returns: { 531347, 531359, 531403, 531406, 531407 }
826631
826708
407578
842307
Returns: { 826663, 826667, 826669, 826673, 826681, 826697, 826699, 826706 }
81440
81459
57773
531231
Returns: { 81457 }
979880
979930
399408
679469
Returns: { 979883, 979886, 979919 }
363645
363679
205282
571619
Returns: { 363659 }
682941
682997
319100
759176
Returns: { 682943, 682967, 682982, 682991 }
660584
660599
418102
841519
Returns: { 660589, 660593 }
665528
665536
97300
397148
Returns: { 665531, 665534 }
143446
143470
74311
894557
Returns: { 143461 }
870813
870866
798733
955286
Returns: { 870823, 870833, 870847 }
889936
889957
431701
787907
Returns: { 889957 }
999000
999100
1
1
Returns: { }
961051
961151
1
100000
Returns: { 961051, 961055, 961056, 961058, 961059, 961060, 961062, 961064, 961065, 961066, 961068, 961070, 961071, 961072, 961074, 961075, 961076, 961077, 961078, 961079, 961080, 961081, 961083, 961085, 961086, 961088, 961089, 961090, 961092, 961093, 961094, 961095, 961096, 961098, 961100, 961101, 961102, 961103, 961104, 961105, 961107, 961108, 961110, 961112, 961113, 961114, 961115, 961116, 961118, 961119, 961120, 961122, 961124, 961125, 961128, 961129, 961130, 961134, 961135, 961136, 961137, 961140, 961142, 961143, 961144, 961146, 961147, 961149, 961150 }
999983
999983
999982
999982
Returns: { 999983 }
999900
1000000
20
1000000
Returns: { 999901, 999902, 999903, 999904, 999905, 999906, 999907, 999908, 999909, 999910, 999911, 999912, 999913, 999914, 999915, 999916, 999917, 999918, 999919, 999920, 999921, 999922, 999923, 999924, 999925, 999926, 999927, 999928, 999929, 999930, 999931, 999932, 999933, 999934, 999935, 999936, 999937, 999938, 999939, 999940, 999941, 999942, 999943, 999944, 999945, 999946, 999947, 999948, 999949, 999950, 999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964, 999965, 999966, 999967, 999968, 999969, 999970, 999971, 999972, 999973, 999974, 999975, 999976, 999977, 999978, 999979, 999980, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998 }
999900
999999
999978
999982
Returns: { 999983 }
1
10
1
1
Returns: { 1, 2, 3, 4, 5, 6, 8, 9, 10 }