Convert a number to a sum of digits

Not any sum: we need the shortest sum
Not any digits: you can use only digits of the number

You will be given as input an integer n>0

Let's say n=27. You have to express 27 as a sum, using only the digits [2,7], in the shortest way possible. You don't have to use all the digits of the given number!

So 27=2+2+2+7+7+7. We then take those digits and count them: [2,2,2,7,7,7].
Final answer for n=27 is 6

One more example for n=195 in order to get the shortest sum we have to use the following digits:
[5,5,5,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9] and the answer is 23

The challenge

Given an integer n>0, output the minimum number of digits (contained in the number) that sum up to this number

Test Cases



This is .Shortest answer in bytes wins!

  • \$\begingroup\$ Are there any numbers that cannot sum to themselves/will they be input? \$\endgroup\$
    – Stephen
    Commented Aug 30, 2017 at 23:34
  • 1
    \$\begingroup\$ @Stephen They all can! \$\endgroup\$
    – user73398
    Commented Aug 30, 2017 at 23:40
  • 7
    \$\begingroup\$ @Stephen Because every number can be expressed as d_0 + 10*d_1 + 100* d_2, etc... \$\endgroup\$
    – geokavel
    Commented Aug 31, 2017 at 0:04
  • \$\begingroup\$ Can we take the input as string, char-array or integer-array? \$\endgroup\$ Commented Aug 31, 2017 at 7:32
  • 1
    \$\begingroup\$ @KevinCruijssen String is ok. char-array or integer-array are not. \$\endgroup\$
    – user73398
    Commented Aug 31, 2017 at 9:02

11 Answers 11


Husk, 12 bytes


Handles two-digit numbers pretty fast. Try it online!


Lḟo=⁰ΣṁΠḣ∞d⁰  Input is n, say n = 13.
          d⁰  Digits of n: [1,3]
         ∞    Repeat infinitely: [[1,3],[1,3],[1,3],[1,3]...
        ḣ     Prefixes: [[],[[1,3]],[[1,3],[1,3]],[[1,3],[1,3],[1,3]],...
      ṁ       Map and concatenate
       Π      Cartesian product: [[],[1],[3],[1,1],[3,1],[1,3],[3,3],[1,1,1],[3,1,1],...
 ḟo           Find the first element
     Σ        whose sum
   =⁰         equals n: [3,3,3,3,1]
L             Return its length: 5

Pyth, 12 bytes


Try it online!

Unfortunately it memory errors on inputs as large as 58.


          ./    All lists of integers that sum to [the input]
  f             Filter for:
    -TsM`Q           Remove all occurrences of the digits in the input
   !                 Check if falsey (i.e. an empty list)
le              Length of the last occurrence, which is the shortest because all the
                filtered partitions share the same digit pool
  • \$\begingroup\$ would you mind adding an explanation? \$\endgroup\$
    – Jonah
    Commented Aug 31, 2017 at 1:25
  • \$\begingroup\$ @Jonah Explanation added. \$\endgroup\$
    – notjagan
    Commented Aug 31, 2017 at 1:52
  • 1
    \$\begingroup\$ Thanks. Interesting that Pyth has a primitive that essentially solves the problem in ./ \$\endgroup\$
    – Jonah
    Commented Aug 31, 2017 at 1:54
  • \$\begingroup\$ 12-byte alternative: lef<.{TjQ;./ (filter - proper subset - of input's digits) \$\endgroup\$
    – Mr. Xcoder
    Commented Aug 31, 2017 at 12:33

Mathematica, 78 bytes


finds last test case in 5 sec

  • \$\begingroup\$ A little bit shorter: Length@IntegerPartitions[#, All, Sort@DeleteCases[0]@IntegerDigits@#, 1][[1]] & \$\endgroup\$
    – Kuba
    Commented Sep 1, 2017 at 13:34

R, 78 bytes


Try it online! (golfed version)

Pure brute force algorithm, so it doesn't actually solve all the test cases, and I think it tried to allocate 40,000 GB for the last test case...

T in R defaults to 1 so we get an off-by-one error which we correct at the return step, but we also get F which defaults to 0 which pays off.

ungolfed explanation:

 d <- n%/%10^(0:nchar(n))%%10   # digit list with a 0 appended at end
 d <- unique(d[d>0])            # filter zeros (not technically necessary)
                                # and get unique digits
 x <- 0                         # storage for sums
 i <- 0                         # counter for number of sums done
 while(!any(x==n)){             # until we find a combination
  x <- outer(x,d,"+")           # take all sums of x and d, store as x
  i <- i + 1}                   # increment counter
i}                              # return counter

Try it online! (less golfy version)


Python 2, 168 155 144 bytes

It isn't the shortest it could be, but it's best-first and not real bad, runtime wise.

def h(k):
 if k<0:return
 if`k`in g:return 1
 for d in g:
  if f:return 1+f
print h(int(n)) 

The filter(None... is to remove 0 as a digit, which I learned I could do while making this.

The biggest problem is python stack frames, which realistically don't allow me to run this on the largest inputs. So, it is not a valid solution, really, I played around with increasing the recursion limit which just led to seg-faults. This has to either be done with a loop and a stack or with a lot more cleverness to work in python.

edit: Thanks to caird and Chas Brown for 13 bytes!

  • \$\begingroup\$ You can use input and require the input to be surrounded with quotes. \$\endgroup\$ Commented Aug 31, 2017 at 0:57
  • 2
    \$\begingroup\$ It's perfectly acceptable to fail due to physical limitations, so long as it succeeds in theory, which this does. \$\endgroup\$ Commented Aug 31, 2017 at 1:18
  • \$\begingroup\$ Save 9 bytes by replacing filter(None,sorted(map(int,set(n)))[::-1]) with sorted(set(map(int,n))-{0})[::-1] (although the None thing is pretty nice to know about). \$\endgroup\$
    – Chas Brown
    Commented Aug 31, 2017 at 6:56
  • \$\begingroup\$ @ChasBrown In most cases you can use filter(len,...) for lists and strings and filter(abs,...) for integers and floats. \$\endgroup\$
    – ovs
    Commented Aug 31, 2017 at 8:50

Husk, 13 bytes

Pretty inefficient


Try it online!


JavaScript (ES6), 82 bytes

<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Takes input as a string.

  • \$\begingroup\$ Can you explain why you are using 1/0? \$\endgroup\$
    – Adalynn
    Commented Aug 31, 2017 at 12:23
  • 1
    \$\begingroup\$ @Zacharý I want the shortest sum, i.e. the minimum number of digits. Attempts which lead to an invalid solution mustn't count, so to exclude them, they score Infinity, which doesn't affect the minimum. \$\endgroup\$
    – Neil
    Commented Aug 31, 2017 at 12:49
  • \$\begingroup\$ Oh, didn't realize it's recursive. \$\endgroup\$
    – Adalynn
    Commented Aug 31, 2017 at 14:41
  • \$\begingroup\$ @Zacharý The f= at the beginning is a big clue, since you don't need it for nonrecursive lambdas. \$\endgroup\$
    – Neil
    Commented Aug 31, 2017 at 16:27

Ruby, 70 bytes

->n{w,s=n.digits,0;s+=1while !w.product(*[w]*s).find{|x|x.sum==n};s+1}

Very slow, try all the possible combinations increasing the size until we get to a solution.

Thanks Dennis for Ruby 2.4 on TIO.

Try it online!


Jelly, 23 bytes


Try it online!

This is so inefficient, that it does not run for the test cases after the third one on TIO due to a time limit >_<

Any golfing tips are welcome!


Python 2, 183 176 172 166 161 bytes

def f(n,D=0,p=0,b=0):
	D=D or set(map(int,`n`))-{0}
	while c<min(D or{0}):q=b=f(n-c*d,D,p+c,b);c+=1

Try it online!

Longer than the other Python answer, but performs all test cases combined plus 987654321 in under a second on TIO.

Takes advantage of the fact that if d1<d2 are digits, then there need be at most d2-1 d1's in the sum (since d2 instances of d1 can be replaced with d1 instances of d2 for a shorter sum). Thus, sorting the digits in ascending order, there are "only" at most 9! = 362880 possible sums to consider; and a maximum recursion depth of 9 (regardless of the value of n).


Haskell, 91 bytes

f n=[read[c]|c<-show n,c>'0']#n!!0

Try it online! Example usage: f 58 yields 8. Quick for two-digit numbers, horrendously slow for larger inputs.

The function f converts the input number n into a list of digits while filtering out zeros. Then this list and n itself are handed to the (#) function, which returns a singleton list. !!0 returns the element of this singleton list.

(#) uses singleton and empty lists as option type. Given an input of n=58 and s=[5,8], the idea is to subtract all digits in s from n, then recursively apply (#) and check which digit resulted in the minimum number of steps and return one plus this minimum as result. The first part is computed by (s#).(n-)=<<s, which is the same as concat(map(s#)(map(n-)s)). So in our example first [58-5,58-8] is computed, followed by [[5,8]#53,[5,8]#50] which results in [[7],[7]] or [7,7] after concat. The result is matched on the pattern x:m to make sure the list has at least one element (minimum fails otherwise), then the singleton list of 1 plus the minimum of the result is retuned. If n was smaller zero or the recursive call returned an empty list, we are in a failing branch of the search and an empty list is returned. If n==0 the branch was succeeding and [0] is returned.

Haskell, 101 bytes

f n=[d|d<-[9,8..1],show d!!0`elem`show n]#n!!0

Try it online! A way more efficient approach, checks all test cases in under one second.

This time, the list of digits of the input is computed to be in descending order, which allows (#) to try to use the largest digit as often as possible, then the second largest, and so until a solution is found. The first solution found this way is also guaranteed to be the smallest one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.