Happy Number

Easy Linked List Slow Fast Pointers Original on LeetCode

Happy Number is a easy linked list problem solved with the slow fast pointers pattern. The best approach, optimal (slow and fast pointers), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (remember every value seen) up.

Problem

Start from a positive integer n and repeatedly replace it with the sum of the squares of its digits. For example, 82 becomes 8² + 2² = 68.

The number is called happy if this process eventually produces 1. Otherwise the values cycle forever without reaching 1. Return true if n is happy and false otherwise.

Examples

Example 1

Input
n = 7
Output
true
Why
7 → 49 → 97 → 130 → 10 → 1, so the process reaches 1.

Example 2

Input
n = 2
Output
false
Why
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, and 4 repeats forever without ever hitting 1.

Constraints

  • 1 <= n <= 2^31 - 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (remember every value seen)O(log n)O(log n)
Optimal (slow and fast pointers)O(log n)O(1)

1Brute force (remember every value seen)

TimeO(log n)The first step shrinks n to at most 810 (10 digits × 81), so after one O(log n) step every later value is small and only a bounded number of them appear before a repeat.
SpaceO(log n)The set holds the visited values: one large value plus a bounded number of small ones.

Generate the sequence and store each value in a hash set. If you reach 1, the number is happy. If you meet a value that is already in the set, the sequence is stuck in a loop that does not contain 1.

  1. Create an empty set.
  2. While n != 1 and n is not in the set: add n, then replace n with the sum of the squares of its digits.
  3. Return n == 1.
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = next(n);
        }
        return n == 1;
    }

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

2Optimal (slow and fast pointers)

TimeO(log n)Same bounded number of steps as the set version; fast does twice the work, which is still a constant factor.
SpaceO(1)Only two integers are stored, no set.

Treat the sequence like a linked list where next(x) is the pointer. Move slow one step and fast two steps at a time. If there is a loop, they must meet inside it; if the sequence reaches 1, fast gets there first (1 maps to itself, so they also meet at 1). The answer is whether the meeting value is 1.

  1. slow = n, fast = next(n).
  2. While fast != 1 and slow != fast: slow = next(slow), fast = next(next(fast)).
  3. Return fast == 1.
class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = next(n);
        while (fast != 1 && slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }
        return fast == 1;
    }

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

Edge cases to test

  • n = 1 is already happy
  • Powers of ten such as 10 or 1000000000 reach 1 in one step
  • The largest input 2^31 - 1, whose digit-square sum is still small
  • Numbers that fall into the 4 → 16 → … → 4 loop

Hints

Hint 1

Write a helper that returns the sum of the squares of the digits. How large can that sum be for a 10-digit number?

Hint 2

The sequence either reaches 1 or repeats a value. How do you detect that a value repeats?

Hint 3

Detecting a repeat in a sequence where every value has exactly one successor is cycle detection, the same as in a linked list. Try a slow and a fast pointer.

FAQ

What is the best time complexity for Happy Number?

Optimal (slow and fast pointers) runs in O(log n) time and O(1) extra space. Same bounded number of steps as the set version; fast does twice the work, which is still a constant factor.

Which pattern does Happy Number use?

It is a linked list problem that uses the slow fast pointers pattern. Other problems with the same pattern: Middle of the Linked List, Linked List Cycle, Linked List Cycle II.

Is there a brute force solution for Happy Number?

Yes. Brute force (remember every value seen) takes O(log n) time and O(log n) space. Generate the sequence and store each value in a hash set.

Which edge cases should I test for Happy Number?

n = 1 is already happy; Powers of ten such as 10 or 1000000000 reach 1 in one step; The largest input 2^31 - 1, whose digit-square sum is still small; Numbers that fall into the 4 → 16 → … → 4 loop.