Minimize Those Ones

Question

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

Answer 1

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 10¹⁴¹⁵ 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 10¹⁵.

Answer 2

Pyth, 19 16 bytes

ffqQvs+R1Y^c3"+-

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.

Explanation:

ffqQvs+R1Y^c3"+-
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.

Answer 3

JavaScript (ES6), 92 bytes

f=(n,i=3)=>eval([...s=i.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n?f(n,i+1):s.length-1

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

Explanation

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.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')