NumCombine

SRM 121 · 2002-11-26 · by mitalub

Class Name: NumCombine

Return Type: int

Method Name: numCombos

Arg Types: (string, int)

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.

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

"3463245"
4
Returns: 298

"000000000000000"
1
Returns: 4782969

"012345678912345"
234233
Returns: 4726757

"0"
100
Returns: 1

"01010101"
1000
Returns: 2102

"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.

"927572819283748"
123456789
Returns: 4780782

Watch out for math with big numbers.

Submissions are judged against all 33 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NumCombine with a public method int numCombos(string input, int target) · 33 test cases · 2 s / 256 MB per case