index.html

<link rel="stylesheet" href="https://casual-effects.com/markdeep/latest/apidoc.css?"">

        **Digit-based problems**

Programming problems on the digits of integers can be solved by

1. converting the integer to a string, or
2. using arithmetic operators such as remainder, % and integer division, '//' that allow us to perform digit-by-digit manipulation.

Method 1 allows one to use string indexing and slicing to extract the digits and manipulate them. For example, if n = 1234, and taking m = str(n) we have:

• m[0] => '1', giving us the leading digit
• m[-1] => '4', giving us the trailing digit
• m[::-1] => '4321' is number-string reversed, etc.

Bear in mind that the result of the above operations is a string again (Python doesn't magically convert it back to an integer just because they happen to be digits), so typically you would want to convert the result back to an integer when you're done.

Method 2 is the one you really need to be familiar with. In simplest terms, given an integer n:

1. n % 10 lets us extract the last digit (1234%10 => 4)
2. n // 10 gives us what remains when the last digit is chopped off (1234//10 => 123)
3. Do the above two steps in a loop (as explained below) and you can process the entire number digit by digit starting at the end.

---

If you have trouble remembering these operations, use this analogy: Suppose you wanted to pay someone $1230, and you only had 10 dollar bank notes. (But you had as many of them as you like, for the sake of the analogy!) So you could pay them the exact amount by handing them 123 notes, after which you owe them nothing. This is basically saying that 1230 // 10 = 123 and 1230 % 10 = 0.

What if you had owed them $1234? Well, now you still hand them 123 notes, paying them a total of $1230, but now you still owe them $4. This is saying that 1234 // 10 = 123 and 1234 % 10 = 4.

Of course, in the tutorial here we're dealing with chopping up digits, but this analogy transfers over directly because we work in base-10 (corresponding to our usage of 10 dollar notes).

---

Here's the simplest possible example, one that prints the digits of the number backwards, one by one:

def printDigits(n):
  while n > 0:
    d = n % 10
    print(d)
    n //= 10

The basic pattern here is

while n > 0: # as long as there are digits remaining
  d = n % 10 # get the last digit
  # ... do something with it
  # ...
  n //= 10 # chop the last digit off

The chopping process makes the number smaller and the loop stops when n becomes 0. (We're assuming n was a positive int to begin with.)

Also notice that the loop runs as many times as there are digits. This gives us a simple way to count digits:

def digitCount(n):
  count = 0
  while n > 0:
    d = n % 10
    count += 1
    n //= 10
  return count

Here's how we would sum up all the digits:

def digitSum(n):
  sum = 0
  while n > 0:
    d = n % 10
    sum += d
    n //= 10
  return sum

So passing in 1234 as input should return 10 (=1+2+3+4).

Let's write a function that returns True if a certain digit x is in the given positive integer d, and False otherwise. We're using the same pattern as before, what's new is that we inspect every digit we chop off and compare it with x. As soon as we find a match (if at all), we can return True. But only after having seen all the digits in the number (corresponding to the loop having finished) can we return False.

def digitPresent(n, x):
  while n > 0:
    d = n % 10
    if d == x:
      return True
    n //= 10
  
  # If execution reaches this point, then the digit wasn't found
  return False

Notice that we can conveniently work with the digits from right to left but not the other way around. One can write a helper that first reverses a number and then works on the digits of the reversed number from right to left. This is effectively like working on the original number from the leftmost digit forward. However, writing this function is a bit more complex; we need to build up a new number m as we decimate n.¹

TODO

<style class="fallback">body{visibility:hidden}</style><script>markdeepOptions={tocStyle:'medium'};</script> <script src="https://casual-effects.com/markdeep/latest/markdeep.min.js?" charset="utf-8"></script>

Footnotes

1. Of course, if you were allowed to use lists, it would be a simple matter of putting all the digits in a list and then iterating over it backwards. But we're assuming that we're not allowed to use strings or lists for these problems. ↩