An interesting discovery with Python division

While solving a LeetCode problem, I discovered an interesting property of Python's division.

This is the LeetCode question:

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.

If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corresponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.
Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters '0' or '1'
s[0] == '1'

First, I tried to solve it using the rules directly:

class Solution:
    def numSteps(self, s: str) -> int:
        num = int(s, 2)

        step = 0
        current_num = num

        while current_num != 1:
            if current_num % 2 == 0:
                # even
                current_num = current_num / 2
            else:
                # odd
                current_num += 1

            step += 1

        return step

This seemed to pass the test, but there was a test case that it didn't quite go through:

input: s = "1111011110000011100000110001011011110010111001010111110001"
Output: 82
Expected: 85

I was confused, so I tried to debug why this was happening. After printing out the current number at each step, I found that the stdout was giving out unexpected output:

1 278675673186014706
2 1.3933783659300736e+17
3 6.966891829650368e+16
4 3.483445914825184e+16
5 1.741722957412592e+16
6 8708614787062960.0
7 4354307393531480.0
8 2177153696765740.0
9 1088576848382870.0
10 544288424191435.0
...

After doing some research, I found there's a difference between using / and // in Python.

In Python:

• / is True Division operator, which is designed to always return a float (a decimal number), even if the numbers divide perfectly.

Now, the issue was that the number is 18 digits long (10¹⁷), which meant that the float "runs out of space". So it rounds the result and displays it in scientific notation (1.3933... x 10¹⁷).

Python float

Unlike integers, which can grow as long as you have RAM, floats have a fixed size (64-bit). Because the size is fixed, there are very specific physical limits to how large a float can be and how many digits of precision it can maintain.

Now the crucial part which caused the error is because a float can only stay accurate for about 15 to 17 significant decimal digits. Beyond 17 digits, the "least significant" numbers are rounded or lost because there simply aren't enough bits to store them.

x = 1.234567890123456789  # 19 digits
print(x)
# Output: 1.2345678901234567 (Last digits are lost)

With this, I realized that I need to use // division in order to get an accurate result. This is because by using //, you stay within Python's arbitrary-precision integers, avoiding the precision limits of floats. meaning it keeps it as an int and will never lose a single digit regardless of how large the number is.

class Solution:
    def numSteps(self, s: str) -> int:
        num = int(s, 2)

        step = 0
        current_num = num

        while current_num != 1:
            if current_num % 2 == 0:
                # even
                current_num = current_num // 2
            else:
                # odd
                current_num += 1

            step += 1

        return step