Input: n = 23
Output: True

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

We can simulate the process of identifying a happy number by repeatedly summing the squares of each digit of a number, and then applying the same process to the resulting sum.

According to the problem statement, this process could conclude in one of two ways:

• Case 1: the process continues until the final number is 1.
• Case 2: the process gets stuck in an infinite loop.

If we diagram both scenarios, we observe something interesting:

This looks quite similar to a linked list problem. In particular, the problem of determining if a linked list has a cycle (case 2) or doesn’t (case 1).

We can reduce this problem to the same cycle detection challenge as the Linked List Loop problem. By applying the fast and slow pointer technique (i.e., Floyd's Cycle Detection algorithm), we can efficiently determine if a cycle exists.

However, in this problem, we don't have an actual linked list to perform the fast and slow pointer algorithm on. Therefore, we need to find a way to traverse the sequence of numbers generated in the happy number process.

Conveniently, we already know what the “next” number in the sequence is for any number x. As described in the problem statement, the next number can be calculated by summing the square of each digit of x. So, if each number were a node in a linked list, we could get the “next” node by calculating the next number in the sequence.

Getting the next number in the sequence
To calculate the next number of x, we need a way to access each digit of x. This can be done in two steps:

1. The modulo operation (x % 10) is used to extract the last digit of a number x.

2. Divide x by 10 (x = x / 10) to truncate the last digit, positioning the next digit as the new last digit.

We can see this unfold in full below for x = 123:

Now that we have a way to traverse the sequence, we can implement Floyd’s Cycle Detection algorithm. To start, set the fast and slow pointers at the start of this sequence. Then move the pointers as follows:

• Advance the slow pointer one number at a time (slow = get_next_num(slow)).

• Advance the fast pointer two numbers at a time
  (fast = get_next_num(get_next_num(fast))).

If the fast and slow pointers meet during the process, it indicates the presence of a cycle, meaning the number is not a happy number. Otherwise, the algorithm will end when we reach 1, in which case the number is a happy number.

Implementation

def happy_number(n: int) -> bool:
    slow = fast = n
    while True:
        slow = get_next_num(slow)
        fast = get_next_num(get_next_num(fast))
        if fast == 1:
            return True
        # If the fast and slow pointers meet, a cycle is detected. Hence, 'n' is not
        # a happy number.
        elif fast == slow:
            return False
    
def get_next_num(x: int) -> int:
    next_num = 0
    while x > 0:
        # Extract the last digit of 'x'.
        digit = x % 10
        # Truncate (remove) the last digit from 'x' using floor division.
        x //= 10
        # Add the square of the extracted digit to the sum.
        next_num += digit ** 2
    return next_num

int nextNum(int x) {                 // sum of squares of digits
    int total = 0;
    while (x > 0) {
        int d = x % 10;
        total += d * d;
        x /= 10;
    }
    return total;
}

bool happyNumber(int n) {
    int slow = n;
    int fast = nextNum(n);
    while (fast != 1 && slow != fast) {
        slow = nextNum(slow);              // one step
        fast = nextNum(nextNum(fast));     // two steps
    }
    return fast == 1;
}

private int nextNum(int x) {          // sum of squares of digits
    int total = 0;
    while (x > 0) {
        int d = x % 10;
        total += d * d;
        x /= 10;
    }
    return total;
}

public boolean happyNumber(int n) {
    int slow = n;
    int fast = nextNum(n);
    while (fast != 1 && slow != fast) {
        slow = nextNum(slow);              // one step
        fast = nextNum(nextNum(fast));     // two steps
    }
    return fast == 1;
}

Complexity Analysis

Time complexity: The time complexity of happy_number is $O(\log(n))$. The full analysis of this time complexity is quite complicated and beyond the scope of interviews. For interested readers, please see the detailed analysis below.

Space complexity: The space complexity is $O(1)$.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Interview Tip

Tip: Visualize the problem.
At first glance, this problem seems like it requires mathematical reasoning to solve. However, when we visualized the problem, we were able to formulate a solution using an algorithm we already know (Floyd’s Cycle Detection). Visualizing a problem can help uncover hidden patterns or data structures that can lead to the solution.

Happy Number Time Complexity Analysis

The following time complexity analysis establishes an upper bound on the steps required to determine a happy number. In this analysis, we define the "next number" of a number $n$ as the result obtained by summing the squares of the digits of $n$.

1) Upper limit for the next number For any number $n$ with a fixed number of digits, the maximum value for its successor is achieved when all its digits are 9. For instance, the maximum next number from a 3-digit number happens when this 3-digit number is 999.

2) Size of the next number relative to the number of digits

• If a number $n$ has 1 or 2 digits, it’s possible for the next number to be larger than $n$ (e.g., the next number of 99 is 162, which is one digit longer).

• If a number $n$ has 3 or more digits, the next number is always smaller than the original value of $n$. The table below highlights how the largest number with 3 or more digits has a smaller next number.

3) Implications for cycles Since the next number is always smaller for numbers with three or more digits, it means a cycle can only commence in the happy number process once the number falls below 243 (the next number of 999). This is because we’ve observed that any number $n$ larger than 243 will have the next number smaller than $n$. However, once we fall below 243, the next number can potentially be larger, potentially cycling back to a previous number.

4) Time complexity for numbers less than 243 Once a number falls below 243, the algorithm will take less than 243 steps to either converge to 1 or to cycle back to a previous number in the sequence. Therefore, since the length of the cycle or the number of steps to reach 1 is bounded by 243, the time complexity of Floyd’s cycle detection algorithm for numbers less than 243 is $O(1)$.

5) Time complexity for numbers greater than 243 The number of digits in a number is approximately equal to $\log(n)$ (base 10). So, the calculation of the next number of $n$ will take approximately $\log(n)$ steps (i.e., get_next_num will take $\log(n)$ steps to execute).

Let's call $n$’s next number $n^2$. The next number after $n^2$ ($n^3$) will take approximately $\log(n^2)$ steps to calculate. The next number after $n^3$ ($n^4$) will take approximately $\log(n^3)$ steps to calculate, and so on. From this, we can summarize the time complexity of this process as $O(\log(n)+\log(n^2)+\log(n^3)+…)$. Since we've established that $n>n^2>…>n^k$ where $n^k$ is the last number greater than 243, the dominant component of this time complexity is $O(\log(n))$. So, the time complexity for numbers greater than 243 is $O(\log(n))$.

Conclusion When $n$ is less than 243, the time complexity is O(1), and when $n$ is greater than 243, the time complexity is $O(\log(n))$. Therefore, the overall time complexity of the algorithm is $O(\log(n))$.

Interview Tip

Tip: Don’t waste time on complex proofs if it isn’t an important part of the interview.

During an interview, correctly deciphering the exact time of an algorithm like the one used to solve this problem isn't usually expected. In situations like this, you can instead make an educated guess about how the algorithm's runtime would grow with larger inputs based on the behavior of the algorithm. Mention any assumptions you make when discussing your estimates. It might also be helpful to mention what parts of the problem or the solution make it difficult to analyze the time complexity. In this problem, it’s initially unclear how many steps the happy number process would take before reaching 1 or revealing a cycle.