0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please could you provide the exact wording of the error, "but shows runtime error for larger inputs". \$\endgroup\$ – Peilonrayz Feb 13 at 15:58
  • \$\begingroup\$ @Peilonrayz edited my question. Sorry for the wrong word. It'll be time limit error. After the 29th input, code forces shows time limit exceeded ... \$\endgroup\$ – Nehal Samee Feb 13 at 16:02
  • 2
    \$\begingroup\$ Please could you include a description of the challenge. Questions and answers on the Stack Exchange network should be self-contained, as you never know when another site is going to 404, or if our users are behind a firewall that blocks it. Please could you also include the exact error description too. Thank you. \$\endgroup\$ – Peilonrayz Feb 13 at 16:07
  • \$\begingroup\$ @Peilonrayz I've added the description... \$\endgroup\$ – Nehal Samee Feb 13 at 16:13
  • \$\begingroup\$ It would also help including the memory and time constraints, and some test cases, most importantly the one that fails for you. How big is that number? I couldn't tell without creating an account on that site. \$\endgroup\$ – gazoh Feb 13 at 16:33
3
\$\begingroup\$
  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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ will it run faster? \$\endgroup\$ – Nehal Samee Feb 13 at 16:40
  • \$\begingroup\$ @NehalSamee It should take less memory as it doesn't have to actually create a list, and definitely takes less memory. But it's fairly minor. I added a bit at the bottom of how you could get more efficiency out of it. It's a little trickier. \$\endgroup\$ – Cruncher Feb 13 at 16:41
  • 1
    \$\begingroup\$ @NehalSamee Perhaps you need to use a smarter algorithm. Like, say the number is 9123123123, then you can actually subtract 9 * ceil(123123123 / 9) immediately, because you know the 9 won't change until the 123123123 has been subtracted causing the 9 to become an 8 \$\endgroup\$ – Cruncher Feb 13 at 17:55
  • 1
    \$\begingroup\$ That's probably part of the trick indeed, excluding calculations based on calculations you've already done in the past. Got something to do with Memoization I think. \$\endgroup\$ – Mast Feb 13 at 18:56
  • 1
    \$\begingroup\$ @Mast I managed to do it! Thanks for the suggestion. See the edit. This is a huge rabbithole from the original question, but I believe this is what they're expecting for optimal efficiency. \$\endgroup\$ – Cruncher Feb 13 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.