Partial answers for [1000][1000] and complete for [1001][1001]


#1

used MeMoization. I mean what kind of sorcery is this :expressionless:


#2

I think they made the tests in such way that it is not going to pass if you use memoization. However, using tabulation you only need the previous step results to build the results for current step, thus the memory usage is O(S). I think the guys from interviewbit want to teach us which technique is the best choice (and I think they are right). Thumb up : when I saw this problem my mind pointed the the coin change (i.e. in how many ways you can make the change). Basically, you can apply a “similar” idea here (stacking a new digit and satisfy the given constraint). The only thing that you must be careful is that when the sum is bigger than 9 (the greatest leading digit) you must offset. I’ve spent… too much time to solve this bug, but I’m happy that I figure it out the overall solution fast :).

P.S. The guys from interviewbit are obsessed with numbers :). The problem is not hard… but you must figured out how numbers are formed… this is the n’th problem with number construction.