12
\$\begingroup\$

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

Example
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

Input->Output

1->1  
2->1  
10->10  
58->8  
874->110  
1259->142  
12347->1765  
123456->20576  
3456789->384088  

This is .Shortest answer in bytes wins!

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

11 Answers 11

4
\$\begingroup\$

Husk, 12 bytes

Lḟo=⁰ΣṁΠḣ∞d⁰

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

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 12 bytes

lef!-TsM`Q./

Try it online!

Unfortunately it memory errors on inputs as large as 58.

Explanation

lef!-TsM`Q./
          ./    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
\$\endgroup\$
  • \$\begingroup\$ would you mind adding an explanation? \$\endgroup\$ – Jonah Aug 31 '17 at 1:25
  • \$\begingroup\$ @Jonah Explanation added. \$\endgroup\$ – notjagan Aug 31 '17 at 1:52
  • 1
    \$\begingroup\$ Thanks. Interesting that Pyth has a primitive that essentially solves the problem in ./ \$\endgroup\$ – Jonah Aug 31 '17 at 1:54
  • \$\begingroup\$ 12-byte alternative: lef<.{TjQ;./ (filter - proper subset - of input's digits) \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 12:33
2
\$\begingroup\$

Mathematica, 78 bytes

(t=1;While[(s=IntegerPartitions[x=#,t,IntegerDigits@x])=={},t++];Tr[1^#&@@s])&  

finds last test case in 5 sec

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

R, 78 bytes

function(n){while(all(F-n)){F=outer(F,n%/%10^(0:nchar(n))%%10,"+")
T=T+1}
T-1}

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:

function(n){
 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)

\$\endgroup\$
2
\$\begingroup\$

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.

n=input()
g=sorted(set(n)-{0})[::-1]
def h(k):
 if k<0:return
 if`k`in g:return 1
 for d in g:
  f=h(k-int(d))
  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!

\$\endgroup\$
  • \$\begingroup\$ You can use input and require the input to be surrounded with quotes. \$\endgroup\$ – caird coinheringaahing Aug 31 '17 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\$ – Jonathan Allan Aug 31 '17 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 Aug 31 '17 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 Aug 31 '17 at 8:50
0
\$\begingroup\$

Husk, 13 bytes

Pretty inefficient

VVo=⁰ΣMṖNṘ⁰d⁰

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 82 bytes

f=(n,l=0,a=n,[c,...b]=a)=>n?1/c?Math.min(!+c|+c>n?1/0:f(n-c,l+1,a),f(n,l,b)):1/0:l
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Takes input as a string.

\$\endgroup\$
  • \$\begingroup\$ Can you explain why you are using 1/0? \$\endgroup\$ – Zacharý Aug 31 '17 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 Aug 31 '17 at 12:49
  • \$\begingroup\$ Oh, didn't realize it's recursive. \$\endgroup\$ – Zacharý Aug 31 '17 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 Aug 31 '17 at 16:27
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 23 bytes

D;0ṗµḟ€0
ÇS€=µT
Çị1ĿL€Ṃ

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!

\$\endgroup\$
0
\$\begingroup\$

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}
	d=min(D);c=0;D=D-{d}
	q=[p+n/d,b][n%d>0]
	while c<min(D or{0}):q=b=f(n-c*d,D,p+c,b);c+=1
	return[q,b][q>b>0]

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

\$\endgroup\$
0
\$\begingroup\$

Haskell, 91 bytes

f n=[read[c]|c<-show n,c>'0']#n!!0
s#n|n>0,x:m<-(s#).(n-)=<<s=[1+minimum(x:m)]|1<3=[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
s@(d:r)#n|n>=d,[x]<-s#(n-d)=[x+1]|1<3=r#n
s#n=[0|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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy