Array: mathematical sequence

An array of integers A[i] (i > 1) is defined in the following way: an element A[k] ( k > 1) is the smallest number greater than A[k-1] such th开发者_开发知识库at the sum of its digits is equal to the sum of the digits of the number 4* A[k-1] .

You need to write a program that calculates the N th number in this array based on the given first element A[1] .

INPUT: In one line of standard input there are two numbers seperated with a single space: A[1] (1 <= A[1] <= 100) and N (1 <= N <= 10000).

OUTPUT: The standard output should only contain a single integer A[N] , the Nth number of the defined sequence.

Input: 7 4

Output: 79

Explanation: Elements of the array are as follows: 7, 19, 49, 79... and the 4th element is solution.

I tried solving this by coding a separate function that for a given number A[k] calculates the sum of it's digits and finds the smallest number greater than A[k-1] as it says in the problem, but with no success. The first testing failed because of a memory limit, the second testing failed because of a time limit, and now i don't have any possible idea how to solve this. One friend suggested recursion, but i don't know how to set that.

Anyone who can help me in any way please write, also suggest some ideas about using recursion/DP for solving this problem. Thanks.

This has nothing to do with recursion and almost nothing with dynamic programming. You just need to find viable optimizations to make it fast enough. Just a hint, try to understand this solution:

http://codepad.org/LkTJEILz

Here is a simple solution in python. It only uses iteration, recursion is unnecessary and inefficient even for a quick and dirty solution.

def sumDigits(x):
    sum = 0;
    while(x>0):
        sum += x % 10
        x /= 10
    return sum

def homework(a0, N):
    a = [a0]
    while(len(a) < N):
        nextNum = a[len(a)-1] + 1
        while(sumDigits(nextNum) != sumDigits(4 * a[len(a)-1])):
            nextNum += 1
        a.append(nextNum)
    return a[N-1]

PS. I know we're not really supposed to give homework answers, but it appears the OP is in an intro to C++ class so probably doesn't know python yet, hopefully it just looks like pseudo code. Also the code is missing many simple optimizations which would probably make it too slow for a solution as is.

It is rather recursive.

The kernel of the problem is:

Find the smallest number N greater than K having digitsum(N) = J.

• If digitsum(K) == J then test if N = K + 9 satisfies the condition.

• If digitsum(K) < J then possibly N differs from K only in the ones digit (if the digitsum can be achieved without exceeding 9).

• Otherwise if digitsum(K) <= J the new ones digit is 9 and the problem recurses to "Find the smallest number N' greater than (K/10) having digitsum(N') = J-9, then N = N'*10 + 9".

• If digitsum(K) > J then ???

In every case N <= 4 * K

9 -> 18 by the first rule

52 -> 55 by the second rule

99 -> 189 by the third rule, the first rule is used during recursion

25 -> 100 requires the fourth case, which I had originally not seen the need for.

Any more counterexamples?