Interconvert strings and integers

1. Problem statement

Convert a string representation of an integer into the integer and vice versa (Aziz et al., 2018, p. 75).

2. Insights

For the simplest case, there is only a single digit and doing the conversion is just a numerical lookup (using ASCII values directly)

3. Solutions

3.1. int to str

code(1/9) 🔗
def int_to_str(n: int) -> str:

If the number is negative, we have to keep track of this separately. It simplifies our algorithm if we always only work with positive integers, so we also make the number positive if necessary as a preparatory step.

code(2/9) 🔗
    negative = False
    if n < 0:
        negative = True
        n = -n

Now we have to repeatedly divide the number and get the modulo as well. This way we only ever concern ourselves with one digit at a time.

One thing to keep in mind is that the string result will never be empty, because an integer type's "constructor" is some numeric value. So we use a while True loop conditional here because we know that we must do some amount of building up the result string.

Another thing to keep in mind is that we build up a list in reverse because it technically requires less copying (we avoid moving array elements by appending to it).

code(3/9) 🔗
    digits = []
    while True:
        digit = n % 10
        digit_ascii_codepoint = ord('0') + digit
        digits.append(chr(digit_ascii_codepoint))
        n //= 10
        if n == 0:
            break

Note that we had to use the ord() and chr() built-ins. These make working with ASCII codepoints easier.

code(4/9) 🔗
    res = "-" if negative else ""
    res += "".join(reversed(digits))
    return res

3.1.1. Complexity

  • Time: \(O(d)\) where \(d\) is the number of digits in the input number.
  • Space: \(O(d)\) (same as above).

3.2. str to int

code(5/9) 🔗
def str_to_int(s: str) -> int:

If the input is the empty string, we return a default value, zero.

code(6/9) 🔗
    res = 0

    if not s:
        return res

Now we have to consider if the number is negative, as before.

code(7/9) 🔗
    negative = False
    if s[0] == "-":
        negative = True
        s = s[1:] # Drop the "-" character.

We now loop through the input string in reverse. We start with the rightmost digit and work our way left.

code(8/9) 🔗
    for power, digit in enumerate(reversed(s)):
        num = ord(digit) - ord("0")
        res += (10**power) * num

    if negative:
        res *= -1

    return res

3.2.1. Complexity

  • Time: \(O(d)\) where \(d\) is the number of digits in the input number.
  • Space: \(O(1)\) because we only need to use a single integer variable for additional space (beyond the input string, whose memory allocation is not part of our algorithm's behavior).

3.2.2. Variation with functools

This version uses functools.reduce() from the functools module to iterate in through the input string in the opposite direction (left-to-right). The trick is to multiply whatever previous (partial) sum we have by 10 on each subsequent iteration.

code(9/9) 🔗
def str_to_int_functional(s: str) -> int:
    res = functools.reduce(
        lambda partial_sum, digit: partial_sum * 10 + (ord(digit) - ord('0')),
        s[s[0] == "-":],
        0)
    if s[0] == "-":
        res *= -1
    return res

Note the s[s[0] == "-":] trick — this simplifies to s[1:] (skipping the first character) only if the first character is a negative sign symbol.

One other difference is that we no longer have to raise anything to a power using the ** operator, because we spread this out over each iteration by multiplying the partial sum by 10.

4. Tests

🔗
from hypothesis import given, strategies as st
import unittest

import functools

code

class Test(unittest.TestCase):
    cases = [
        (-234,  "-234"),
        (-1,  "-1"),
        (0,   "0"),
        (1,   "1"),
        (123, "123"),
    ]

    def test_simple_cases(self):
        for given_int, expected in self.cases:
            self.assertEqual(int_to_str(given_int), expected,
                             msg=f'{given_int=}')

        for expected, given_str in self.cases:
            self.assertEqual(str_to_int(given_str), expected,
                             msg=f'{given_str=}')

    @given(st.integers(min_value=-1000000, max_value=1000000))
    def test_random(self, given_int: int):
        got_str = int_to_str(given_int)
        got_int = str_to_int(got_str)
        got_int_functional = str_to_int_functional(got_str)
        # Check roundtrip.
        self.assertEqual(got_int, given_int, msg=f'{given_int=}')
        self.assertEqual(got_int_functional, given_int, msg=f'{given_int=}')

if __name__ == "__main__":
    unittest.main(exit=False)

5. References

Aziz, A., Lee, T.-H., & Prakash, A. (2018). Elements of Programming Interviews in Python: The Insiders’ Guide. CreateSpace Independent Publishing Platform (25 July. 2018).