Happy Number - Practice Coding Problems

Happy Number - Problem

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.

Input & Output

Example 1 — Happy Number

$ Input: n = 19

› Output: true

💡 Note: 19 → 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1. Since we reached 1, 19 is a happy number.

Example 2 — Unhappy Number

$ Input: n = 2

› Output: false

💡 Note: 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. We detect a cycle that doesn't include 1, so 2 is not happy.

Example 3 — Single Digit Happy

$ Input: n = 1

› Output: true

💡 Note: 1 → 1² = 1. Already at 1, so it's happy by definition.

Constraints

1 ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Start with positive integer n

Transform

Replace with sum of squares of digits

Check

Reaches 1 (happy) or cycles (unhappy)

Key Takeaway

🎯 Key Insight: Every number either reaches 1 (happy) or enters an infinite cycle (unhappy)

Asked in

G Google 12 a Amazon 8 M Microsoft 6 🍎 Apple 4

A happy number reaches 1 through digit square sums, while unhappy numbers cycle forever. The key insight is detecting cycles efficiently. Best approaches: Hash Set O(log n) space or Floyd's Algorithm O(1) space. Time: O(log n), Space: O(1) optimal.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set - Track All Seen Numbers	O(log n)	O(log n)	Store every number we've seen to detect cycles
Mathematical Optimization - Hardcode Known Cycles	O(log n)	O(1)	Use mathematical properties to optimize cycle detection
Floyd's Cycle Detection - Tortoise and Hare	O(log n)	O(1)	Use slow and fast pointers to detect cycles without extra space

Hash Set - Track All Seen Numbers — Algorithm Steps

Step 1: Create a hash set to store seen numbers
Step 2: While n ≠ 1 and n not in seen set, add n to set and transform it
Step 3: If n = 1, return true; otherwise return false (cycle detected)

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n=19, empty set

Transform

Add to set, calculate sum of squares

Detect

Continue until 1 or cycle found

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int getNext(int num) {
    int total = 0;
    while (num > 0) {
        int digit = num % 10;
        total += digit * digit;
        num /= 10;
    }
    return total;
}

bool solution(int n) {
    int seen[1000] = {0}; // Simple array for small cycles
    int count = 0;
    
    while (n != 1) {
        // Check if n already seen
        for (int i = 0; i < count; i++) {
            if (seen[i] == n) return false;
        }
        seen[count++] = n;
        n = getNext(n);
        if (count >= 1000) return false; // Safety check
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each transformation reduces digits, limited cycles exist

⚡ Linearithmic

Space Complexity

O(log n)

Hash set stores at most O(log n) numbers before cycle

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set - Track All Seen Numbers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler