PROBLEM STATEMENT
When we were little we all played the game 24. The object of the game is given
4 integers, construct the number 24 using the standard operations - addition,
subtraction, multiplication, division.
For example: if you are given the numbers 3, 6, 7, 10 it is possible to get 24
in a number of ways.
(a) (7 * (6 / 3)) + 10
(b) ((7 * 6) / 3) + 10
(c) ((7 / 3) * 6) + 10
(d) (7 / (3 / 6)) + 10
* note there are other ways that are basically similar by using commutativity
of addition and multiplication. ((7 * 6) / 3) + 10 could be rearranged to ((6
* 7) / 3) + 10 without changing the value.
You are to write a program where given an int[] of numbers, and a target value,
returns the smallest integer greater than or equal to the target value which is
possible to construct using the numbers given and the 4 standard mathematical
operators. If no integer greater than or equal to the target value is
possible, return -1.
DEFINITION
Class Name: NumberGame
Method Name: nextPoss
Parameters: int[], int
Returns: int
Method signature (be sure your method is public): int nextPoss (int[] nums,
int target);
NOTES
- The only allowable operations are addition, subtraction, multiplication, and
division.
- You are only allowed to use the numbers given in nums. You may not use
numbers not in the nums.
- You must use every number in nums exactly the amount of times it appears. If
nums = {3, 4, 3}, you must use 3 twice, and 4 once.
- You may use each operator as many times as you like (i.e. you may use
division more than once).
- You may not concatenate two numbers, i.e. {2, 3} cannot become 23. You may
only use one of the four given operators.
- The total number of operators you use must be one less than the number of
elements in nums.
- Subtraction can not be used as a negation (i.e. if nums = {2}, -2 is not
legal), it is strictly a binary operator.
- Note that non-integer division can be used in intermediate results. For
example, ((2 / 3) / (1 / 3)) = (.666 / .333) = 2 is a possible way to construct
2 from the numbers {1,2,3,3}.
- You may rearrange the order of nums. For example, if you are given {4,11},
you can construct 11 - 4 = 7.
- Only integral final results will be considered. So 11/4 = 2.75 should not be
considered as a possible answer. See example 6.
- Watch out for division by 0.
TopCoder will ensure that:
- nums will contain between 1 and 4 elements inclusive.
- Each element of nums will be between 0 and 50 inclusive.
- target will be between 1 and 999999999 inclusive.
EXAMPLES:
1. nums = {7}, target = 7.
Since the only element is our target, we can make a 7. Return 7.
2. nums = {1, 2}, target = 3.
1 + 2 = 3. Return 3.
3. nums = {2, 2}, target = 2.
There is no way to get 2 using both 2's. Using only one 2 is illegal. The
closest value greater than or equal to 2 is 4 (2+2 or 2*2). Return 4.
4. nums = {0, 1, 5, 3}, target = 3 (watch for division by 0).
0 + 1 - (3 - 5) = 3. Return 3.
5. nums = {3, 4, 6, 13}, target = 26.
((13 / 6) * 3) * 4 = 26. Return 26.
6. nums = {11, 4}, target = 2.
There is clearly no way to get 2. 11/4 = 2.75, but this is not an integer.
The next value greater than 2 that we can make is 11-4=7. Return 7.
7. nums = {13, 7, 5, 2}, target = 7.
(2 * (13 - 7)) - 5 = 7. Return 7.
8. nums = {13, 7, 5, 2}, target = 33.
There is no way to get 33 from these numbers. You may need to exhaust all
the possibilities to see this result. The next greatest integer possible to
construct is 34, which can be constructed as 13+(7*(5-2)). Return 34.
9. nums = {6, 12, 31, 3}, target = 744.
31 * (12 / (3 / 6)) = 744. Return 744.
10. nums = {1, 2, 3, 4}, target = 100.
No number greater than or equal to 100 can be constructed using these
numbers. Return -1.