Problem Statement
Once upon a time, there lived a powerful wizard who created spheresCount magical spheres. These spheres, when connected together, were a source of unimaginable power. To prevent anyone else from using them, the wizard created fakeSpheresCount spheres that are indistinguishable from the real ones, but don't hold any magical power.
You are determined to find out which spheres are real, and use them to rule the world. To accomplish this, you want to gather a team of gnomes to try every combination of spheresCount spheres out of (spheresCount + fakeSpheresCount) spheres, even if it takes centuries. You will assign combinations to each gnome beforehand, and you will not test any combination more than once. Unfortunately, the gnomes have a labor union that won't allow some gnomes to have more work than others. Therefore, you must select a team size that will allow you to assign an equal number of combinations to each gnome.
Return the maximum possible team size less than or equal to gnomesAvailable that allows even distribution of the work.
Definition
- Class:
- MagicalSpheres
- Method:
- divideWork
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable)
- (be sure your method is public)
Constraints
- spheresCount will be between 1 and 1,000,000,000, inclusive.
- fakeSpheresCount will be between 1 and 1,000,000,000, inclusive.
- availableGnomes will be between 1 and 100000, inclusive.
Examples
3
1
3
Returns: 2
We have a total of four spheres, lets call them {a,b,c,d}. We need to check all triplets to find which of them are real. The different triplets are: {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}. Since there are four possibilities to check, we can divide it between two gnomes, by assigning two to each of them.
3
3
50
Returns: 20
With three fake spheres, there are 20 triplets to check. You can use 20 gnomes and assign one of the triplets to each of them.
4
3
4
Returns: 1
15634
456
5000
Returns: 4990
1
1
1
Returns: 1
3
4
7
Returns: 7
5
10
15
Returns: 13
17
15
9
Returns: 9
8
5
7
Returns: 3
25
200
53
Returns: 53
1
1
100000
Returns: 2
1
1000000000
100000
Returns: 52579
1000000000
1
100000
Returns: 52579
1000000000
1000000000
100000
Returns: 99999
99999
1
100000
Returns: 100000
99998
1
100000
Returns: 99999
1000000000
7
100000
Returns: 91793
104728
1
100000
Returns: 1
254972796
976428979
36598
Returns: 36597
922654481
37093235
92878
Returns: 92877
189456684
239786691
77218
Returns: 77217
443269984
808717823
48700
Returns: 48699
929681485
148354056
59910
Returns: 59909
35476864
499212869
32000
Returns: 31999
364294062
269626489
68006
Returns: 68005
284557229
441937746
67394
Returns: 67393
898331181
50587384
18195
Returns: 18194
62203742
873907697
87521
Returns: 87520
156696250
364145116
19676
Returns: 19675
684008726
787171029
80309
Returns: 80307
744730271
676698948
51879
Returns: 51876
729764506
132986785
53318
Returns: 53316
24162769
663036338
57881
Returns: 57880
915479710
298082273
85571
Returns: 85570
134573091
343763223
40534
Returns: 40530
923880115
115208846
31881
Returns: 31880
752117869
123598459
95928
Returns: 95927
146469395
584773967
28967
Returns: 28965
602512778
33
8969
Returns: 8909
239195732
438598351
75315
Returns: 75314
60166845
582531294
59164
Returns: 59163
465861224
383282877
74363
Returns: 74362
389568456
150298080
83026
Returns: 83024
573292766
821355779
31100
Returns: 31099
463289430
873453124
35589
Returns: 35588
400736091
303627748
50889
Returns: 50888
174908467
647921742
36724
Returns: 36723
636023265
995817552
48850
Returns: 48849
871188082
507984543
7263
Returns: 7261
520652328
260010826
41049
Returns: 41046
700063172
242555982
3145
Returns: 3145
931279817
2
46537
Returns: 31377
634129184
86013470
77700
Returns: 77700
845043508
153315566
86955
Returns: 86955
780703191
217547373
78435
Returns: 78435
213205823
628125890
80548
Returns: 80548
867049395
827703788
39160
Returns: 39160
958635490
421975925
2943
Returns: 2943
889523678
315652698
1803
Returns: 1803
269010297
121766544
89018
Returns: 89018
296810828
55830206
60288
Returns: 60288
6998558
213579889
74998
Returns: 74998
968569159
613354729
64689
Returns: 64684
399421581
281
40572
Returns: 40553
709866671
75
73236
Returns: 73159
128053769
1
75791
Returns: 390
500000000
500000000
92153
Returns: 92153
123456789
432242
100000
Returns: 99997
1000000000
1000000000
99991
Returns: 99991
998537333
999999111
98337
Returns: 98337
686542271
789445031
97305
Returns: 97301
1000000000
500000000
100000
Returns: 99999
2
1
100000
Returns: 3
979878945
645666449
100000
Returns: 100000
112901988
1
100000
Returns: 1
2
2
4
Returns: 3
999999937
1
100000
Returns: 98
12
1
100000
Returns: 13
123456789
712345678
100000
Returns: 99997
982451652
1
100000
Returns: 1
1
1000
100000
Returns: 1001
40999998
1
100000
Returns: 1
1
784234
100000
Returns: 11705