The Great Julya Calendar

Question

Challenge

An integer is provided as an input. In each step, we have to subtract a number from the input which already exists as a digit of the input. In this way, we have to make the input equal to zero(0). The problem is to output the minimum number of such steps.

Code

n=int(input())
count=0

while n:
    l=list(int(i) for i in str(n))
    n=n-max(l)
    count+=1
    if n == 0:
        break

print (count)

---

The code outputs the correct results; but on larger input it exceeds the time limits. That is, for every input memory consumption increases and the time limit is reached up until the 30th test case.

Answer 1

1. You don't need to actually build a whole list of the digits. It's unnecessary memory consumption. You can pass a generator to max.
2. use python's -= syntax when subtracting from a variable.
3. The break is unnecessary as it's covered by the while condition

Final code:

n=int(input()) 
count=0

while n:
    n -= max(int(i) for i in str(n))
    count += 1

print (count)

This code would be fairly difficult to improve much further for efficiency. You could really penny pinch performance on the generator by building a generator that will stop iteration after it encounters a 9, as it knows it cannot ever get a number bigger than that. You could also use modulo and integer division logic to extract digits to avoid having to go from int -> str -> int.

---

Okay. This is now straying pretty far from the original question, but I liked the challenge and @Mast in the comments expired me by mentioning memoization.

To utilize memoization the problem needed to be formulated in a recursive way where I can store the result of intermediate calls to avoid re-computation of things already computed. The strategy was to define the recursive function "compute_count(previous_max, rest)", where previous_max is initially called with 0, and rest as the entire number.

The idea is that a max, num pair uniquely identifies a solution, so every time we end up with the same max, num pair we can use the precomputed result. Formulating the problem in this way led to writing a fairly complicated function, but on the example you provided in the comments it returns instantly. The memoization table ends up with 293 entries, so it's well within your 256MB limit.

Anyway, here's the final code:

memoization_table = {}

def compute_count(previous_max, rest):
    global memoization_table 
    original_rest = rest

    if (previous_max, rest) in memoization_table:
        return memoization_table[(previous_max, rest)] 

    num_digits = len(str(rest))

    if num_digits == 1:
        memoization_table[(previous_max, original_rest)] = 1, min(0, rest-previous_max) 
        return 1, min(0, rest-previous_max) 

    sum_count = 0
    while rest > 0:
        s = str(rest).zfill(num_digits)
        new_max = max(previous_max, int(s[0])) 
        new_rest = int(s[1:])
        count, leftover = compute_count(new_max, new_rest) 

        sum_count += count 
        rest -= new_rest
        rest += leftover

    memoization_table[(previous_max, original_rest)] = sum_count, rest
    return sum_count, rest

print(compute_count(0, 1278564645)[0])
print(len(memoization_table))

I imported the length of the memoization table just to see the memory implications of the solution, and it turned out to be very reasonable. Obviously remove this from any submitted solutions.

Here's the output of the run:

$ python compute_count.py 
154026551
293

---

Example:

For calculating 24, these are the function calls made:

compute_count(0,24)
compute_count(2,4)
compute_count(2,0)
compute_count(1,8)
compute_count(1,0)
compute_count(0,9)

To calculate compute_count(0, 24):

1. get new previous_max, which is the max of 0 and 2.

2. do a compute_count on 2,4. Since this is a single digit number, it's our base case, and we return that we can get to 0 with a single move (as is the case with all single digit numbers).

3. Since we did a compute_count(2,4) which told us it did a single computation, we need to subtract the number computed for (4) from our running number (24). This gives us a remainder of 20, and a running count of 1.

4. The new previous_max is still 2, as our remainder is 20.

5. do a compute_count on 2,0. This one is a special case. Getting from 0 to 0 should technically take no moves, but we have additional logic for these cases because the previous max is 2. Which means this isn't really a single digit number, and I need to return the "leftover" which is -2 so the caller can account for the underflow of the subtraction. So this function returns a count of 1, and a leftover of -2

6. Since we passed 0 to compute_count, we subtract 0 from our 20 which keeps us at 20. But because a leftover of -2 was returned, we also have to add that to our 20 which gives us a total of 18 for this iteration.

7. The above process continues in kind until our remaining is 0 or less and we've summed all the counts.