0

Write a recursive function replace_digit(n, d, r) which replaces each occurrence of digit d in the number n by r.

replace_digit(31242154125, 1, 0) => 30242054025

My code is as such

def replace_digit(n, d, r):
    y=str(n)
    if len(y)==0:
        return ''
    else:
        if y[0]== str(d):
            return str(r) + replace_digit(str(n)[1:],d,r)
        else:
            return y[0]+ replace_digit(str(n)[1:],d,r)

However, the answer I get is in a string format. Any idea how to convert into an integer format? I have been stuck for quite some time on this :(

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Wei Han
  • 1
  • 1
    Return an integer (`int(string_value)`), and convert the returned value *from a recursive call* to a string again. – Martijn Pieters Mar 10 '21 at 10:55
  • Ah, there is a problem there: numbers starting with `0` are going to lose that digit. Do you have any further instructions as for what direction you need to process the numbers in? – Martijn Pieters Mar 10 '21 at 11:07
  • Not really, I just need to get the number shown, where '1's become '0's – Wei Han Mar 10 '21 at 11:11

1 Answers1

1

If your recursive function must return an integer, then return integers. You can always convert the returned integer back into a string for recursive calls.

You'll have to stop when you run out of digits before calling, so only recurse if there are 2 or more characters in y.

However, this approach a big problem: leading zeros are dropped when converting to int():

>>> int('025')
25

You have two options here:

  • Pad the number when you convert to a string (using str.zfill() or format(), and use the length of the value you passed into the recursive call).
  • Recurse from the end. This would also allow you to not use strings.

Here is an approach using zero-padding:

def replace_digit(n, d, r):
    nstr = str(n)
    first, rest = nstr[0], nstr[1:]
    if rest:
        rest = str(replace_digit(rest, d, r)).zfill(len(rest))
    if first == str(d):
        first = str(r)
    return int(first + rest)

Note that you always want to separate out the first character from the tail anyway, so I used variables for both.

This way, you can use if rest: to guard against recursing when there are no digits left, and you can call str() on the return value. The function returns the int() conversion of the (possibly replaced first value) with the updated rest value.

Demo:

>>> replace_digit(31242154125, 1, 0)
30242054025

Recursing from the opposite end would not have problems with zeros, except if the input value was 0 to begin with. However, you could instead use division and modules operations to work on the integer value directly:

  • number % 10 gives you the right-most digit, as an integer.
  • number // 10 gives you the remaining numbers, again as integer.

You could combine the two operations into one using the divmod() function. Personally, I don't do so, as I don't think it particularly improves readability, and using the operators is slightly faster when using CPython.

You can re-combine the recursive call result with the (possibly replaced) last digit by multiplying the returned value by 10 again:

def replace_digit(n, d, r):
    head, last = n // 10, n % 10
    if head:
        head = replace_digit(head, d, r)
    if last == d:
        last = r
    return (head * 10) + last

This works for any natural number, including 0:

>>> replace_digit(0, 1, 0)
0
>>> replace_digit(0, 0, 1)
1
>>> replace_digit(31242154125, 1, 0)
30242054025
>>> replace_digit(31242154125, 4, 9)
31292159125
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343