Happy Number

LeetCode 202 | Difficulty: Easy

Easy

Problem Description

Write an algorithm to determine if a number n 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.

- 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.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

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

Topics: Hash Table, Math, Two Pointers

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 36 ms)

Metric	Value
Runtime	36 ms
Memory	14.6 MB
Date	2020-04-04

Solution

public class Solution {
    public bool IsHappy(int n) {
        long slow = n, fast = n;
    do
    {
        slow = digSquare(slow);
        fast = digSquare(fast);
        fast = digSquare(fast);
        if(fast == 1 ) return true;
    } while (slow != fast);
    return false;
}


long digSquare(long n)
{
    long sum = 0;
    while(n!=0)
    {
        var temp = n%10;
        sum += temp*temp;
        n /= 10;
    }
    return sum;
}
}

📜 1 more C# submission(s)

Submission (2020-02-11) — 40 ms, 14.6 MB

public class Solution {
    public bool IsHappy(int n) {
        long slow = n, fast = n;
    do
    {
        slow = digSquare(slow);
        fast = digSquare(fast);
        fast = digSquare(fast);
        if(fast == 1 ) return true;
    } while (slow != fast);
    return false;
}


long digSquare(long n)
{
    long sum = 0;
    while(n!=0)
    {
        var temp = n%10;
        sum += temp*temp;
        n /= 10;
    }
    return sum;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.