15
2
Overview
Given a list of digits, find the fewest operations to make 100
Input
A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus (+) or minus (-) operators may be added between each so that the total sum is equal to 100.
Output
The number of operators added, followed by the full sequence of digits and operators. The two can be separated by a space, tab, or new line sequence.
Examples
valid
Input: 123456789
Output: 3 123–45–67+89
Invalid
Input: 123456789
Output:
6
1+2+34-5+67-8+9
(There are ways of solving this with fewer operations)
Related – Adám – 2017-07-04T12:23:07.770
Do we have to use all of the digits? Can we only use
+
and-
? Can we assume we will always be able to make100
from the input? – TheLethalCoder – 2017-07-04T12:50:56.283@TheLethalCoder All digits must be used, and must remain in the same order. The only thing that can be changed is adding + and -. – CyberJacob – 2017-07-04T13:31:04.820
6Some more test cases would be much welcome. – Arnauld – 2017-07-04T13:36:02.450
Is the input guaranteed to lead to at least one solution? If not, what's the expected output? – Arnauld – 2017-07-04T13:56:20.253
@Arnauld Yes, there will always be at least 1 possible solution – CyberJacob – 2017-07-04T14:11:59.523
Is output such as
{3, "123-45-67+89"}
(use language-specified tuple structure) acceptable? – Keyu Gan – 2017-07-04T16:56:18.3902Can you confirm that signs cannot be prepended to the first digit? That is, given input
299399
, would-299+399
be valid? – Luis Mendo – 2017-07-04T17:08:13.323May we use our languages native operators (or even any alternative but consistent characters) in the output? – Jonathan Allan – 2017-07-04T17:26:17.270
1Is '0' a digit? E.g., is '10808' a valid input? Is '1 108-08' a valid response? – Chas Brown – 2017-07-04T19:07:07.427
@KeyuGan yes, as long as the two components are obviously seperate – CyberJacob – 2017-07-04T23:12:54.927
@LuisMendo no, signs can only be added between digits – CyberJacob – 2017-07-04T23:13:37.087
@ChasBrown yes, 0 is a digit – CyberJacob – 2017-07-04T23:13:48.963
@JonathanAllan Yes – CyberJacob – 2017-07-04T23:14:00.797