202. Happy Number

NeetCode: Happy Number · LeetCode: 202. Happy Number · Difficulty: Easy

Start with a positive integer n and repeatedly replace it by the sum of the squares of its digits. n is happy if this process reaches 1; otherwise it loops forever in a cycle that does not contain 1. Return whether n is happy.

Example

Input:  n = 19    Output: true    (19 -> 82 -> 68 -> 100 -> 1)
Input:  n = 2     Output: false   (2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...)

Brute force: remember every value seen

The sequence either reaches 1 or repeats a value. Keep a HashSet of everything seen; set.add(x) returns false when x is already present, so a failed add means the sequence is in a cycle and n is not happy. The sequence cannot grow without bound: a number with d digits maps to at most 81 * d, which is smaller than the number itself once it has more than three digits, so the sequence must eventually repeat or reach 1. Even Integer.MAX_VALUE (10 digits) maps to a value of at most 810, so the sum never overflows int.

import java.util.HashSet;
import java.util.Set;

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

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1) {
            if (!seen.add(n)) {
                return false;
            }
            n = next(n);
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isHappy(19));
        System.out.println(s.isHappy(2));
        System.out.println(s.isHappy(1));
        System.out.println(s.isHappy(Integer.MAX_VALUE));
    }
}

true
false
true
false

Time: roughly O(log n): after the first step the value is small (at most a few hundred), so the remaining walk has a bounded length. Space: O(1) in practice for the same reason, but the set is still extra memory.

Optimal: Floyd's fast and slow pointers

Treat the sequence as a linked list where each value points to its successor. Floyd's algorithm detects the cycle without storing values: move slow one step and fast two steps per round. If there is a cycle, they meet inside it. If fast reaches 1 first, the number is happy, since 1 maps to itself.

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

    public boolean isHappy(int n) {
        int slow = n;
        int fast = next(n);
        while (fast != 1 && slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }
        return fast == 1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isHappy(19));
        System.out.println(s.isHappy(2));
        System.out.println(s.isHappy(1));
        System.out.println(s.isHappy(Integer.MAX_VALUE));
    }
}

true
false
true
false

Time: roughly O(log n) (the digit sums dominate; the cycle length is bounded by a small constant). Space: O(1).

Both versions have the same running time; the second uses constant memory.