LeetCode 1342. Number of Steps to Reduce a Number to Zero

September 13, 2020

Looks like they give us an $O(n)$ algorithm for this. We could just follow the steps they describe and keep a counter.

Can we do better? Is there a mathematical trick to do this in constant time? I thought about this for a long time and couldn't figure it out. The closest we got was finding the closest power of 2 ( $log_2(num)$ )and then trying to compute the meaning of the difference. That's kinda hard because each -1 is of a different magnitude, depending on how many division by 2 came before it, and they aren't evenly distributed.

How about bit manipulation? My girlfriend came up with:

Convert $num$ to binary.
Return $len(num)$ - 1 + <number of 1's in $num$ >.

This bit manipulation solution is likely much faster than mine in practice. Interestingly, it's still $O(log(n))$ in Python3 since the bin() function is $O(log(n))$ .

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.numberOfSteps(14), 6)
        self.assertEqual(self.s.numberOfSteps(8), 4)
        self.assertEqual(self.s.numberOfSteps(123), 12)

    def test_minimal_steps(self):
        self.assertEqual(self.s.numberOfSteps(0), 0)
        self.assertEqual(self.s.numberOfSteps(1), 1)
        self.assertEqual(self.s.numberOfSteps(2), 2)
        self.assertEqual(self.s.numberOfSteps(3), 3)
        self.assertEqual(self.s.numberOfSteps(4), 3)

    def test_large_numbers(self):
        self.assertEqual(self.s.numberOfSteps(1273), 17)

class Solution:

    def numberOfSteps (self, num: int) -> int:
        c = 0
        while num > 0:
            if num & 1:
                num -= 1
            else:
                num >>= 1
            c += 1
        return c

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