Problem Statement
You are developing a new calculator with a square root function. To make things simple for your clients, you have decided to approximate square roots as simple fractions, rather than displaying a long sequence of digits.
You will be given N and D and should return the fraction closest to sqrt(N) for which the denominator is not greater than D. The fraction should be returned in the form "A/B" where A and B are positive integers with no common factors greater than one.
Definition
- Class:
- CalcRoot
- Method:
- approximate
- Parameters:
- int, int
- Returns:
- String
- Method signature:
- String approximate(int N, int D)
- (be sure your method is public)
Constraints
- N will be between 1 and 1000000, inclusive.
- D will be between 1 and 1000, inclusive.
Examples
4
10
Returns: "2/1"
5
3
Returns: "7/3"
sqrt(5) = 2.236
12
10
Returns: "31/9"
sqrt(12) = 3.464
23743
763
Returns: "98462/639"
991746
903
Returns: "837522/841"
69
5
Returns: "25/3"
29
32
Returns: "70/13"
53
1
Returns: "7/1"
73
61
Returns: "487/57"
21
1
Returns: "5/1"
41
81
Returns: "397/62"
17
25
Returns: "33/8"
65
7
Returns: "8/1"
46
47
Returns: "156/23"
622311
92
Returns: "11833/15"
264041
50
Returns: "16957/33"
756386
81
Returns: "38267/44"
426901
1
Returns: "653/1"
426901
13
Returns: "5227/8"
267545
68
Returns: "33621/65"
267545
68
Returns: "33621/65"
407369
15
Returns: "2553/4"
407369
19
Returns: "2553/4"
330966
93
Returns: "15533/27"
630297
511
Returns: "299305/377"
845032
412
Returns: "369541/402"
844899
763
Returns: "649863/707"
987955
551
Returns: "268369/270"
30230
123
Returns: "21038/121"
30230
123
Returns: "21038/121"
831401
705
Returns: "504232/553"
822089
958
Returns: "651911/719"
802089
958
Returns: "836485/934"
306283
374
Returns: "3874/7"
852501
187
Returns: "169889/184"
852301
187
Returns: "123709/134"
679471
361
Returns: "266249/323"
409096
787
Returns: "292300/457"
677285
297
Returns: "153896/187"
673283
297
Returns: "236315/288"
513729
826
Returns: "493840/689"
864738
810
Returns: "555158/597"
893057
725
Returns: "670017/709"
405537
11
Returns: "7005/11"
923273
1000
Returns: "29787/31"
911323
1000
Returns: "371352/389"
964997
1000
Returns: "564847/575"
932436
1000
Returns: "588067/609"
971073
1000
Returns: "707539/718"
963341
1000
Returns: "770477/785"
943089
1000
Returns: "585590/603"
959967
1000
Returns: "851428/869"
958146
1000
Returns: "948505/969"
927561
1000
Returns: "608679/632"
927561
1000
Returns: "608679/632"
938401
1000
Returns: "968711/1000"
942491
1000
Returns: "560163/577"
917827
1000
Returns: "844985/882"
950896
1000
Returns: "357876/367"
923141
1000
Returns: "592815/617"
938598
1000
Returns: "687857/710"
945350
1000
Returns: "798251/821"
915881
1000
Returns: "915865/957"
990329
1000
Returns: "560271/563"
1
1
Returns: "1/1"
2
1
Returns: "1/1"
1
2
Returns: "1/1"
2
1000
Returns: "1393/985"
999993
1000
Returns: "856997/857"
998001
1000
Returns: "999/1"
998000
1000
Returns: "998999/1000"
998002
1000
Returns: "999001/1000"
671348
1000
Returns: "667777/815"
234728
1000
Returns: "210752/435"
896649
1000
Returns: "549211/580"
872865
1000
Returns: "895033/958"
105462
1000
Returns: "280908/865"
117609
1000
Returns: "158782/463"
161840
1000
Returns: "238560/593"
767095
1000
Returns: "606081/692"
894579
1000
Returns: "233618/247"
468639
1000
Returns: "279990/409"
499455
1000
Returns: "677039/958"
771858
1000
Returns: "459484/523"
102134
776
Returns: "172895/541"
382098
938
Returns: "505021/817"
24806
789
Returns: "99067/629"
931221
522
Returns: "465129/482"
362520
956
Returns: "443745/737"
470436
829
Returns: "317564/463"
798602
554
Returns: "488824/547"
718484
369
Returns: "305996/361"
736680
564
Returns: "402543/469"
131689
616
Returns: "134995/372"
656496
948
Returns: "470752/581"
138067
857
Returns: "259730/699"
923780
659
Returns: "592059/616"
983580
914
Returns: "906465/914"
57840
963
Returns: "231120/961"
953235
871
Returns: "850390/871"
951698
998
Returns: "973599/998"
949181
706
Returns: "661522/679"
945035
883
Returns: "858390/883"
206654
711
Returns: "323215/711"
996183
959
Returns: "367297/368"
991746
841
Returns: "837522/841"
987222
608
Returns: "499776/503"
11745
1000
Returns: "62532/577"
15770
1000
Returns: "91798/731"
40602
1000
Returns: "162207/805"
150290
1000
Returns: "264005/681"
193857
1000
Returns: "131207/298"
218378
1000
Returns: "376184/805"
87
83
Returns: "513/55"
23743
763
Returns: "98462/639"
991746
903
Returns: "837522/841"
999999
1000
Returns: "999999/1000"
536538
923
Returns: "676086/923"
1
1
Returns: "1/1"
990021
498
Returns: "494514/497"
980002
999
Returns: "980051/990"
999999
1
Returns: "1000/1"
593021
982
Returns: "686140/891"
998634
1000
Returns: "864409/865"