Problem Statement
Once there was a planet with S inhabitants.
The planet then faced N bad years in a row. Each year exactly one bad thing happened: either the planet got hit by a small asteroid, or the planet got visited by the space dragon.
Preserved historical records tell us the following:
- The space dragon always ate exactly one inhabitant.
- An asteroid hit always killed exactly one half of the population.
- During the N years nobody was born and nobody died for another reason.
Given all this information we would like to determine the current population of this planet. However, the answer to this question is not necessarily unique. Count all options that are consistent with all the above information, and return that count.
Definition
- Class:
- DecreasingPopulation
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int S, int N)
- (be sure your method is public)
Notes
- One half of zero is zero. Hence, it is possible that after everyone died there were some additional asteroid hits.
Constraints
- S will be between 1 and 5,000, inclusive.
- N will be between 1 and 5,000, inclusive.
Examples
24
1
Returns: 2
The original population consisted of S = 24 people. There was N = 1 bad event. The answer is 2 because now there are two options: If there was an asteroid hit, the current population is 12. If there was a dragon visit, the current population is 23.
17
1
Returns: 1
As the original population was odd, we can deduce that the only bad event must have been a dragon visit and thus the current population must be 16.
2
2
Returns: 1
Regardless of what the first event was, it killed one person. The second event must have been a dragon visit that killed the other person. Thus, there is only one valid option: the current population is 0.
30
3
Returns: 4
1
5000
Returns: 1
5000
5000
Returns: 1
2883
54
Returns: 245
3525
4536
Returns: 1
3717
86
Returns: 369
2814
2109
Returns: 355
4198
74
Returns: 348
3215
336
Returns: 780
3429
92
Returns: 377
194
840
Returns: 1
6
66
Returns: 1
3945
4479
Returns: 1
75
70
Returns: 5
4650
3504
Returns: 575
1885
65
Returns: 247
4287
4211
Returns: 40
2942
78
Returns: 320
1983
273
Returns: 555
4596
73
Returns: 353
2896
4924
Returns: 1
2801
85
Returns: 338
4712
1606
Returns: 1555
1955
100
Returns: 325
290
1029
Returns: 1
2736
56
Returns: 250
2973
4738
Returns: 1
3143
82
Returns: 336
4425
2072
Returns: 1179
796
91
Returns: 203
1860
2744
Returns: 1
1791
80
Returns: 273
903
3414
Returns: 1
4954
72
Returns: 353
2346
1958
Returns: 196
4549
66
Returns: 322
2925
4364
Returns: 1
4632
52
Returns: 270
3965
2558
Returns: 706
4610
99
Returns: 439
3240
2132
Returns: 556
4255
64
Returns: 305
4968
934
Returns: 1478
1697
74
Returns: 256
3977
2074
Returns: 954
4945
85
Returns: 405
1223
3637
Returns: 1
125
60
Returns: 35
4481
679
Returns: 1292
612
67
Returns: 153
4189
4480
Returns: 1
3904
100
Returns: 421
3569
2995
Returns: 289
272
88
Returns: 92
2171
4986
Returns: 1
4235
93
Returns: 405
3866
2581
Returns: 645
183
86
Returns: 51
1991
1732
Returns: 132
2835
77
Returns: 313
1508
1448
Returns: 32
3849
62
Returns: 295
1048
807
Returns: 123
1120
96
Returns: 249
4667
2819
Returns: 926
4321
75
Returns: 355
886
2187
Returns: 1
3637
50
Returns: 243
1003
3393
Returns: 1
551
73
Returns: 151
170
2165
Returns: 1
342
58
Returns: 102
1485
4192
Returns: 1
4023
62
Returns: 292
4053
4328
Returns: 1
3716
86
Returns: 372
4648
82
Returns: 389
605
61
Returns: 144
1234
4452
Returns: 1
2772
90
Returns: 353
383
1922
Returns: 1
502
74
Returns: 146
1009
182
Returns: 300
5000
200
Returns: 724
100
5000
Returns: 1
2000
200
Returns: 476
1
2
Returns: 1