unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 202: Happy Number

link

We run until we see a repeated number and check if that is 1.

Say n is an m digit number. So, n = d_{m-1} \cdot 10^{m-1} + d_{m-2} \cdot 10^{m-2} + \cdots + d_1 \cdot 10^1 + d_0 \cdot 10^0. Let G(n) = \sum_{i=0}^{m-1} d_i^2. The maximum value of G(n) is when digits are all 9‘s. In other words, the maximum value of G(n) = 9^2 \cdot m = 81 \cdot m. Since m = \mathcal{O}(\lg{n}), G(n) = \mathcal{O}(\lg{n}). So, one step of sum of digit squared reduces n to \lg{n}. Thus the number of steps before we reach the cycle is \lg^*{n}.

Time: \mathcal{O}(\lg^*{n}), space: \mathcal{O}(\lg^*{n}).

class Solution:
    def isHappy(self, n: int) -> bool:
        def sum_of_digit_squared(n):
            sq_sum = 0
            while n > 0:
                n, d = divmod(n, 10)
                sq_sum += (d * d)
            return sq_sum

        seen = set()
        while n not in seen:
            seen.add(n)
            n = sum_of_digit_squared(n)
        
        return n == 1

The sequence of numbers: n, G(n), G^2(n), \ldots, always ends with a cycle. So, we can consider the sequence as a linked list with cycle and use slow and fast pointer to find cycle head and check if that is 1.

Time: \mathcal{O}(\lg^*{n}), space: \mathcal{O}(1).

class Solution:
    def isHappy(self, n: int) -> bool:
        def next(x):
            sq_sum = 0
            while x > 0:
                x, d = divmod(x, 10)
                sq_sum += (d * d)
            return sq_sum

        slow, fast = n, n
        while True:
            slow = next(slow)
            fast = next(next(fast))
            if slow == fast:
                break
        
        fast = n
        while slow != fast:
            slow = next(slow)
            fast = next(fast)
        
        return slow == 1

Here is a nice little paper on the problem.

tanvirdotzaman

Leave a comment