Array: mathematical sequence

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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?