+ 3

[CHALLENGE] Break a number as a sum of given numbers

Given a positive integer, express it as sum of input integers in any combination. Eg- given: 32 break it as: [4, 5] 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 OR 5 + 5 + 5 + 5 + 4 + 4 + 4 I don't know if this problem is even solvable 😂

11th Apr 2018, 6:00 PM
Aditya Rana
13 Respuestas
+ 4
It is possible by dynamic programming. And mine solution is in O(n^2) time. Do you want hear it?
11th Apr 2018, 6:11 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
+ 2
Bartosz Pieszko i just solved it. though the code is not good right now (I was just trying to make the logic, so didn't end the infinite loop if num can't be broken), I'll share it with u. i am not quite sure what is dynamic programming but do share your code. always ready to learn more! https://code.sololearn.com/cI3y8oZQAjEM/?ref=app
11th Apr 2018, 6:24 PM
Aditya Rana
+ 2
I'll try modifying it while you eat
11th Apr 2018, 6:27 PM
Aditya Rana
+ 2
@Bartosz Pieszko Yes, I also thought about applying dynamic programming here. So I'm starting to work on my code. However, I would really appreciate to see yours as well to compare.
11th Apr 2018, 6:30 PM
Nevfy
+ 1
well it's specifically for 4 and 5 & for 2 numbers to break into. so definitely not a one to be proud of 😂
11th Apr 2018, 6:25 PM
Aditya Rana
+ 1
Yours solution is only for your one input. It probably doesn't work for other inputs. My solution works for every numbers. I will write this after eating.
11th Apr 2018, 6:26 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
+ 1
just discovered a lot of bugs in the logic. definitely not the solution.
11th Apr 2018, 6:48 PM
Aditya Rana
+ 1
by dynamic programming, are you guys pointing towards machine learning kind of solution?
11th Apr 2018, 7:15 PM
Aditya Rana
0
@Aditya Rana You could probably add to the description that program should return "no combinations" if it is impossible like for 17 and (4,7).
11th Apr 2018, 6:33 PM
Nevfy
0
I'm starting too. Count combinations are much easier than count this set of numbers to sum.
11th Apr 2018, 6:34 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
Nah, it's not machine learning. en.wikipedia.org/wiki/Dynamic_programming
11th Apr 2018, 7:34 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
11th Apr 2018, 8:07 PM
Bartosz Pieszko
Bartosz Pieszko - avatar
0
This code gives you all the solutions and lets you precise the numbers allowed in the sum. oneliner of course. https://code.sololearn.com/cWLGyFH7weto/?ref=app
12th Apr 2018, 2:56 PM
VcC
VcC - avatar