Statistics

Problem Statement for "NumCombine"

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

  1. "3463245"

    4

    Returns: 298

  2. "000000000000000"

    1

    Returns: 4782969

  3. "012345678912345"

    234233

    Returns: 4726757

  4. "0"

    100

    Returns: 1

  5. "01010101"

    1000

    Returns: 2102

  6. "123"

    10

    Returns: 6

    This is the example above.

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

  8. "5"

    4

    Returns: 0

    The only possible expression is "5" which evaluates to more than 4.

  9. "4"

    5

    Returns: 1

  10. "927572819283748"

    123456789

    Returns: 4780782

    Watch out for math with big numbers.

  11. "039458092849"

    4892

    Returns: 165469

  12. "34743564543"

    5675

    Returns: 55674

  13. "4357435645"

    5645645

    Returns: 19653

  14. "000000000222"

    2

    Returns: 118096

  15. "0000000200000"

    2

    Returns: 442827

  16. "12312"

    123

    Returns: 69

  17. "1234"

    1234

    Returns: 27

  18. "1"

    1

    Returns: 1

  19. "0"

    1

    Returns: 1

  20. "436"

    564

    Returns: 9

  21. "34643645"

    564

    Returns: 1870

  22. "927572819085748"

    123406789

    Returns: 4780782

  23. "927572819283748"

    123456789

    Returns: 4780782

  24. "0000"

    0

    Returns: 27

  25. "95465431835"

    123456789

    Returns: 59034

  26. "373737373737373"

    99999999

    Returns: 4780782

  27. "95468431545"

    123456789

    Returns: 59034

  28. "932742232343523"

    123456789

    Returns: 4780782

  29. "0"

    0

    Returns: 1

  30. "999999999999999"

    0

    Returns: 2070067

  31. "4857562049325"

    1500

    Returns: 460129

  32. "0000"

    1

    Returns: 27

  33. "293489485868"

    1234567

    Returns: 176499

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.
This problem was used for: