Minimize Those Ones



Your task is to build a natural number using the fewest number of ones and only the operators + or -. For example, the number seven can be written 1+1+1+1+1+1+1=7, but it can also be written as 11-1-1-1-1=7. The first one uses 7 ones, while the latter only uses 6. Your task is to return the minimum number of ones that can be used given the input of some natural number, n.

This is code golf, so the shortest valid code in bytes wins.

Test cases

Input => Output

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21


Posted 2016-05-03T02:25:30.537

Reputation: 137

Question was closed 2016-05-03T15:13:15.293

Nice first challenge. I'd suggest including more test cases. Is "VALID OUTPUTS" a mistake, given that there's a single output? Also, is 0 a valid input, and if so, what should be output? – xnor – 2016-05-03T02:29:17.790

This is an interesting challenge. You may want to add an explanation for the outputs, change VALID OUTPUTS. It's your choice, but generally people like bold or italics instead of CAPITAL LETTERS (they make it look like shouting instead of emphasis). Bold is **bold text**, and italics is *italics text*. You could also use ### Text for bold-er text. Anyway, welcome to PPCG! – NoOneIsHere – 2016-05-03T02:34:35.870

You should make a computer-readable table or list of test cases that people can run their code on. See this tip.

– xnor – 2016-05-03T02:59:08.087


I'm voting to close this question because this question is of a duplicate of the current (active!!) golfing challenge over at Even if the OP is also the author of the original challenge on codefights (which I doubt), the question should be closed until the challenge on codefights isn't active any more.

– Jakube – 2016-05-03T10:18:58.970


@Jakube the direct link could've been helpful, but I agree. I will vote to close.

– NoOneIsHere – 2016-05-03T14:27:03.213

Is it gone yet? – CalculatorFeline – 2016-05-06T21:47:22.360



JavaScript (ES6), 127 126 87 bytes

f=(n,z=2,m=n*9+'',r=m.replace(/./g,1))=>n?m.length+(m<'55'?f(n- --r/10,0)-1:f(r-n,0)):z
Input: <input type="number" oninput="result.textContent=f(this.value)"> Result: <span id="result"></span>

Should work to about 101415 at which point you start running into JavaScript's integer limits. Explanation:

f=(                             Recursive function
 n,                             Parameter
 z=2,                           Zero workaround
 m=n*9+'',                      Magic
 r=m.replace(/./g,1)            Find repunit not less than than n
)=>n?                           Nothing to do if n is zero
 m.length+                      Assume subtracting from repunit
 (m<'55'?                       Should we subtract from repunit?
  f(n- --r/10,0)                No, so subtract previous repuint
   -1:                          Which is one 1 shorter
  f(r-n,0)):                    Subtract from repunit
 z                              Return special case if n is zero

This uses the n*9 magic twice; firstly, it gives me the length of the next repunit, secondly, if the first two digits of n*9 are 55 or higher, then we need to subtract n from that next repunit, otherwise we need to subtract the previous repunit (which is calculated by subtracting 1 and dividing by 10). This should work up to 1015.


Posted 2016-05-03T02:25:30.537

Reputation: 95 035


Pyth, 19 16 bytes


Test suite

Brute force algorithm. The necessary strings are generated by taking all lists whose elements are ['+', '-', ''] of length equal to the number of 1s being tested, appending a 1 to each, and concatenating to a single string. These strings are then evaluated and compared with the input. This is repeated until a successful string is found.

Some strings with a leading + or - are tested, but this isn't a problem. It would be if the input was negative though.

It can run up to length 9 before it becomes too slow.


ffqQvs+R1Y^c3"+-"T    Implicit variable introduction
                      Q = eval(input())
f                     Starting with T = 1 and counting upwards, repeat until true.
                      The value of T where the result is first true is output.
           c3"+-"     Chop "+-" into thirds, giving ['+', '-', '']
          ^      T    Form every list with those elements of length T.
 f                    Filter over those lists, lambda var Y.
      +R1Y            Append a 1 to each element of the list.
     s                Concatenate.
    v                 Eval.
  qQ                  Compare for equality with the input.
                      The inner filter will let through the successful cases.
                      The outer filter will stop when there is a successful case.


Posted 2016-05-03T02:25:30.537

Reputation: 39 268


JavaScript (ES6), 92 bytes

n = <input type="number" oninput="R.textContent=f(this.value)" /><pre id="R"></pre>


Recursive function. This generates all possible permutations of 1s separated by either +, - or nothing. It does this by incrementing a base-3 number, turning it into an array of digits, converting each digit 0 to -, 1 to + and 2 to an empty string, then joining them together with 1s. The resulting string is evald as a JavaScript statement which returns the result of the equation.

Because the operators are joined with 1s in between (like +1+1+1+), there are length - 1 1s. The first operator is ignored (because +1 = 1, <nothing>1 = 1 and it's a number so there will never be a leading 0 for -) and the final operator is also ignored (by appending .0 to the equation).

Higher Output Version, 96 bytes

The other version can't return outputs higher than ~10 because of the recursion call stack limit. This version uses a for loop instead of recursion, so it can return outputs up to ~33. The amount of time required increases exponentially though so I don't recommend testing it.



Posted 2016-05-03T02:25:30.537

Reputation: 10 181

This sounds overcomplicated, I like it. – Bálint – 2016-05-05T06:56:03.047