NumCombine | Topcoder Archive

Problem Statement

Determine the number of ways to insert "+" and "-" signs into a String of digits so the value of the resulting expression is less than or equal to the target.

For example, if the inputted String is "123" and target is 10, the following insertions yield values less than or equal to 10:
1+2+3
1+2-3
1-2+3
1-2-3
12-3
1-23
So the function should return 6.

Definition

Class:: NumCombine
Method:: numCombos
Parameters:: String, int
Returns:: int
Method signature:: int numCombos(String input, int target)
(be sure your method is public)

Notes

At most one sign (+ or -) can be inserted between digits. So 3+-4 is not a valid expression.
The expression must start with a digit. So -3+4 is not a valid expression.

Constraints

input will contain only numerical digits ('0' - '9').
input will have length between 1 and 15, inclusive.
target will be between -1,000,000,000 and 1,000,000,000, inclusive.

Examples

```
"123"
```
```
10
```
```
Returns: 6
```
This is the example above.
```
"0000"
```
```
1
```
```
Returns: 27
```
All possible expressions resulting from the insertion of plus and minus signs into "0000" results in an expression evaluating to 0. Between any digit there can be no sign, a plus sign, or a minus sign, so the total number of combinations is 3 * 3 * 3 = 27. 0+0+0+0 0-0-0-0 00+00 etc...
```
"5"
```
```
4
```
```
Returns: 0
```
The only possible expression is "5" which evaluates to more than 4.
```
"4"
```
```
5
```
```
Returns: 1
```

"927572819283748"

123456789

Returns: 4780782

Watch out for math with big numbers.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.