How to Understand Time Complexity of Happy Number Problem Solution from Leetcode

Question

I have some difficulties in understanding the time complexity analysis for one solution for the Happy Number Question from Leet code, for my doubts on complexity analysis, I marked them in bold and really appreciate your advice

Here is the question:

Link: https://leetcode.com/problems/happy-number/

Question:

Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19

Output: true

Explanation:

1^2(square of 1) + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

Here is the code:

class Solution(object):
    def isHappy(self, n):
        #getnext function will compute the sum of square of each digit of n
        def getnext(n):
            totalsum = 0
            while n>0:
                n,v = divmod(n,10)
                totalsum+=v**2
            return totalsum
        #we declare seen as a set to track the number we already visited
        seen = set()
        #we stop checking if: either the number reaches one or the number was visited #already(ex.a cycle)
        while n!=1 and (n not in seen):
            seen.add(n)
            n = getnext(n)
        return n==1

Note: feel free to let me know if I need to explain how the code works

Time Complexity Analysis:

Time complexity : O(243 * 3 + logN + loglogN + log loglog N)...=O(logN).

Finding the next value for a given number has a cost of O(log n)because we are processing each digit in the number, and the number of digits in a number is given by logN. My doubt: why the number of digits in a number is given by logN? what is N here? the value of a specific number or something else?

To work out the total time complexity, we'll need to think carefully about how many numbers are in the chain, and how big they are.

We determined above that once a number is below 243, it is impossible for it to go back up above 243.Therefore, based on our very shallow analysis we know for sure that once a number is below 243, it is impossible for it to take more than another 243 steps to terminate.

Each of these numbers has at most 3 digits. With a little more analysis, we could replace the 243 with the length of the longest number chain below 243, however because the constant doesn't matter anyway, we won't worry about it. My doubt: I think the above paragraph is related to the time complexity component of 243*3, but I cannot understand why we multiply 243 by 3

For an n above 243, we need to consider the cost of each number in the chain that is above 243. With a little math, we can show that in the worst case, these costs will be O(log n) + O(log log n) + O(log log log N)... Luckily for us, the O(logN) is the dominating part, and the others are all tiny in comparison (collectively, they add up to less than logN), so we can ignore them. My doubt: what is the reasoning behind O(log log n) O(log log log N) for an n above 243?

Answer 1

Using the Leetcode solution

class Solution {

    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}
}

O(243*3) for n < 243

3 is the max number of digits in n

e.g. For n = 243

getNext() will take a maximum of 3 iterations because there are 3 digits for us to loop over.

isHappy() can take a maximum of 243 iterations to find a cycle or terminate, because we can store a max of 243 numbers in our hash set.

O(log n) + O(log log n) + O(log log log N)... for n > 243

1st iteration + 2nd iteration + 3rd iteration ...

getNext() will be called a maximum of O(log n) times. Because log10 n is the number of digits.

isHappy() will be called a maximum of 9^2 per digit. This is the max we can store in the hash set before we find a cycle or terminate.

First Iteration
 9^2 * number of digits
 O(81*(log n)) drop the constant
 O(log n)
+
 Second Iteration
 O(log (81*(log n))) drop the constant
 O(log log n)
+
 Third Iteration
 O(log log log N) 
+
ect ...

Answer 2

Let's say N has M digits. Than getnext(N) <= 81*M. The equality happens when N only has 9's.

• When N < 1000, i.e. at most 3 digits, getnext(N) <= 3*81 = 243. Now, you will have to call getnext(.) at most O(243) times to figure out if N is indeed happy.

• If M > 3, number of digits of getnext(N) must be less than M. Try getnext(9999), getnext(99999), and so on [1].

Notes:

[1] Adding a digit to N can make it at most 10*N + 9, i.e. adding a 9 at the end. But the number of digits increases to M+1 only. It's a logarithmic relationship between N and M. Hence, the same relationship holds between N and 81*M.

Answer 3

Well, my guess for the first doubt is that the number of digits of a base 10 number is given by it's value (N) taken to the logarithm at base 10, rounded down. So for example, 1023 would have floor(log10(1023)) digits, which is 3. So yes, the N is the value of the number. the log in time complexity indicates a logarithm, not specifically that of base 2 or base e.

As for the second doubt, it probably has to do with the work required to reduce a number to below 243, but I am not sure. I'll edit this answer once I work that bit out.