Happy Number

🎯

Happy Number

easyTWO_POINTERAmazonGoogleBloomberg

Imagine a number game where you repeatedly replace a number by the sum of the squares of its digits. Will you eventually reach 1, or get stuck in a loop forever?

💡 This problem involves detecting cycles in a sequence generated by repeatedly applying a function to a number. Beginners often struggle because the sequence is implicit (not stored explicitly) and cycles are not obvious without careful detection.

📋

Problem Statement

Given a positive integer n, determine if it is a happy number. A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Return true if n is a happy number, and false if not.

1 ≤ n ≤ 10^5

💡

Example

Input"19"

Outputtrue

19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1, so 19 is happy.

• 1 → true (smallest happy number)
• 2 → false (enters cycle)
• 7 → true (happy number)
• 100000 → true (large number with trailing zeros)

⚠️

Common Mistakes

Not detecting cycles properly, leading to infinite loops

Code runs forever or times out

✅ Use a set or fast-slow pointers to detect cycles

Incorrectly computing sum of squares of digits

Wrong results or failure on test cases

✅ Carefully extract digits using modulo and integer division

Using recursion without cycle detection

Stack overflow or infinite recursion

✅ Add cycle detection or convert to iterative approach

Assuming all numbers eventually reach 1 without proof

Incorrectly returning true for unhappy numbers

✅ Implement cycle detection to handle loops

Using extra space unnecessarily when fast-slow pointer suffices

Less optimal solution with higher memory usage

✅ Learn and implement Floyd's cycle detection for space optimization

🧠

Brute Force (Using a Set to Detect Cycles)

💡 This approach introduces the fundamental idea of cycle detection by storing all previously seen numbers. It is simple and intuitive, helping beginners understand why cycles occur and how to detect them.

Intuition

Repeatedly compute the sum of squares of digits and store each result. If we reach 1, the number is happy. If we see a number again, a cycle exists and the number is not happy.

Algorithm

1. Initialize an empty set to store seen numbers.
2. While the current number is not 1 and not in the set:
3. Add the current number to the set.
4. Replace the current number with the sum of the squares of its digits.
5. If the loop ends with number 1, return true; otherwise, return false.

💡 The main challenge is to realize that repeating numbers indicate a cycle, and storing them helps detect this.

</>

Code

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)
    return n == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

def get_next(number):Helper function to compute sum of squares of digits

while number > 0:Extract digits one by one from the number

seen = set()Store all numbers seen so far to detect cycles

while n != 1 and n not in seen:Loop until we find 1 or detect a cycle

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

public class HappyNumber {
    public static boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

Set<Integer> seen = new HashSet<>();Keep track of numbers to detect cycles

while (n != 1 && !seen.contains(n)) {Continue until 1 is found or cycle detected

seen.add(n);Add current number to the set

int digit = number % 10;Extract last digit for sum of squares

#include <iostream>
#include <unordered_set>

using namespace std;

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

bool isHappy(int n) {
    unordered_set<int> seen;
    while (n != 1 && seen.find(n) == seen.end()) {
        seen.insert(n);
        n = getNext(n);
    }
    return n == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

unordered_set<int> seen;Track visited numbers to detect cycles

while (n != 1 && seen.find(n) == seen.end()) {Loop until 1 or cycle detected

seen.insert(n);Mark current number as visited

int digit = number % 10;Extract digits for sum of squares

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

const seen = new Set();Store numbers to detect cycles

while (n !== 1 && !seen.has(n)) {Loop until 1 or cycle detected

seen.add(n);Add current number to the set

let digit = number % 10;Extract digits for sum of squares

⏱

Complexity

TimeO(k * log n) where k is number of iterations until cycle or 1

SpaceO(k) for storing seen numbers

Each iteration computes sum of squares in O(log n) digits, and we store each unique number until cycle or 1 is found.

💡 For n=19, about 5-6 iterations happen, so roughly 30 operations total, which is efficient enough for small inputs.

Interview Verdict: Accepted

This approach is simple and works well for the input constraints, making it a good starting point in interviews.

🧠

Fast and Slow Pointer (Floyd's Cycle Detection)

💡 This approach uses two pointers moving at different speeds to detect cycles without extra space, demonstrating a classic cycle detection technique useful in many problems.

Intuition

If a cycle exists, a fast pointer moving twice as fast as a slow pointer will eventually meet the slow pointer inside the cycle. If the sequence reaches 1, no cycle exists.

Algorithm

1. Initialize slow and fast pointers to the starting number.
2. Move slow pointer one step (sum of squares) and fast pointer two steps repeatedly.
3. If fast pointer reaches 1, return true (happy number).
4. If slow and fast pointers meet at a number other than 1, return false (cycle detected).

💡 The key insight is that meeting pointers means a cycle, and reaching 1 means success.

</>

Code

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    slow = n
    fast = get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

slow = nInitialize slow pointer at start

fast = get_next(n)Initialize fast pointer one step ahead

while fast != 1 and slow != fast:Loop until fast reaches 1 or pointers meet

fast = get_next(get_next(fast))Move fast pointer two steps to detect cycle

public class HappyNumber {
    public static boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

int slow = n;Slow pointer starts at initial number

int fast = getNext(n);Fast pointer starts one step ahead

while (fast != 1 && slow != fast) {Loop until cycle detected or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to catch cycle

#include <iostream>

using namespace std;

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

bool isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

int slow = n;Initialize slow pointer at start

int fast = getNext(n);Initialize fast pointer one step ahead

while (fast != 1 && slow != fast) {Loop until cycle or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to detect cycle

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    let slow = n;
    let fast = getNext(n);
    while (fast !== 1 && slow !== fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

let slow = n;Slow pointer starts at initial number

let fast = getNext(n);Fast pointer starts one step ahead

while (fast !== 1 && slow !== fast) {Loop until cycle detected or happy number found

fast = getNext(getNext(fast));Fast pointer moves two steps to catch cycle

⏱

Complexity

TimeO(k * log n) where k is iterations until cycle or 1

SpaceO(1) constant space

Each iteration computes sum of squares in O(log n) digits, but no extra memory is used for cycle detection.

💡 This approach is more memory efficient than brute force, especially for large inputs.

Interview Verdict: Accepted

This is the optimal approach for cycle detection in this problem and is preferred in interviews.

🧠

Mathematical Insight with Known Cycle Detection

💡 This approach uses known facts about cycles in happy numbers to shortcut detection, useful for optimization and demonstrating domain knowledge.

Intuition

All unhappy numbers eventually enter a known cycle: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. If the sequence hits any number in this cycle, it is not happy.

Algorithm

1. Define a set of known cycle numbers for unhappy sequences.
2. Iterate computing sum of squares of digits.
3. If the number becomes 1, return true.
4. If the number is in the known cycle set, return false.

💡 This approach trades memory for speed by using a fixed set of cycle numbers.

</>

Code

def isHappy(n: int) -> bool:
    cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    while n != 1 and n not in cycle_set:
        n = get_next(n)
    return n == 1

# Driver code
if __name__ == '__main__':
    print(isHappy(19))  # Expected: True
    print(isHappy(2))   # Expected: False

Line Notes

cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}Known unhappy cycle numbers to detect loops quickly

while n != 1 and n not in cycle_set:Loop until happy or known cycle detected

def get_next(number):Helper to compute sum of squares of digits

return n == 1Return true if happy, false if cycle detected

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

public class HappyNumber {
    private static final Set<Integer> cycleSet = new HashSet<>();
    static {
        cycleSet.add(4); cycleSet.add(16); cycleSet.add(37); cycleSet.add(58);
        cycleSet.add(89); cycleSet.add(145); cycleSet.add(42); cycleSet.add(20);
    }

    public static boolean isHappy(int n) {
        while (n != 1 && !cycleSet.contains(n)) {
            n = getNext(n);
        }
        return n == 1;
    }

    private static int getNext(int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // true
        System.out.println(isHappy(2));  // false
    }
}

Line Notes

private static final Set<Integer> cycleSet = new HashSet<>();Store known unhappy cycle numbers

while (n != 1 && !cycleSet.contains(n)) {Loop until happy or known cycle detected

cycleSet.add(4);Initialize cycle set with known cycle numbers

return n == 1;Return true if happy, false otherwise

#include <iostream>
#include <unordered_set>

using namespace std;

bool isHappy(int n) {
    static unordered_set<int> cycleSet = {4,16,37,58,89,145,42,20};

    auto getNext = [](int number) {
        int totalSum = 0;
        while (number > 0) {
            int digit = number % 10;
            totalSum += digit * digit;
            number /= 10;
        }
        return totalSum;
    };

    while (n != 1 && cycleSet.find(n) == cycleSet.end()) {
        n = getNext(n);
    }
    return n == 1;
}

int main() {
    cout << boolalpha << isHappy(19) << endl; // true
    cout << boolalpha << isHappy(2) << endl;  // false
    return 0;
}

Line Notes

static unordered_set<int> cycleSet = {4,16,37,58,89,145,42,20};Known cycle numbers stored statically

while (n != 1 && cycleSet.find(n) == cycleSet.end()) {Loop until happy or cycle detected

auto getNext = [](int number) {Lambda to compute sum of squares

return n == 1;Return true if happy, false otherwise

const cycleSet = new Set([4,16,37,58,89,145,42,20]);

function getNext(number) {
    let totalSum = 0;
    while (number > 0) {
        let digit = number % 10;
        totalSum += digit * digit;
        number = Math.floor(number / 10);
    }
    return totalSum;
}

function isHappy(n) {
    while (n !== 1 && !cycleSet.has(n)) {
        n = getNext(n);
    }
    return n === 1;
}

// Test cases
console.log(isHappy(19)); // true
console.log(isHappy(2));  // false

Line Notes

const cycleSet = new Set([4,16,37,58,89,145,42,20]);Known unhappy cycle numbers for quick detection

while (n !== 1 && !cycleSet.has(n)) {Loop until happy or cycle detected

function getNext(number) {Helper to compute sum of squares

return n === 1;Return true if happy, false otherwise

⏱

Complexity

TimeO(k * log n) with small constant due to early cycle detection

SpaceO(1) constant space

Checking membership in a small fixed set is O(1), speeding up cycle detection.

💡 This approach is a practical optimization that leverages known math facts to shortcut cycle detection.

Interview Verdict: Accepted

This approach is efficient and shows domain knowledge, which can impress interviewers.

📊

All Approaches - One-Glance Tradeoffs

💡 The fast-slow pointer approach is the best balance of simplicity and efficiency, and is recommended for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Set for cycle detection)	O(k * log n)	O(k)	No	N/A	Good to mention and understand cycle detection basics
2. Fast and Slow Pointer (Floyd's Cycle Detection)	O(k * log n)	O(1)	No	N/A	Optimal approach to implement in interviews
3. Known Cycle Set Optimization	O(k * log n)	O(1)	No	N/A	Good to mention as an optimization or domain knowledge

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach using a set to detect cycles.Step 3: Explain the fast-slow pointer technique for cycle detection.Step 4: Mention the known cycle optimization if time permits.Step 5: Code the fast-slow pointer approach for optimal space.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Understanding of cycle detection, ability to optimize space, and clear explanation of tradeoffs.

Common Follow-ups

• Can you detect cycles without extra space? → Use fast and slow pointers.
• What if the input number is very large? → The sum of squares reduces number size quickly.
• Can you prove the cycle detection terminates? → Because numbers reduce to a bounded range.
• What is the time complexity? → O(k * log n), k is iterations until cycle or 1.

💡 These follow-ups test deeper understanding of cycle detection and complexity analysis.

🔍

Pattern Recognition

When to Use

1) Problem involves repeated transformation of a number or state; 2) Need to detect if process ends or loops; 3) Cycle detection is required; 4) No explicit data structure given, sequence is implicit.

Signature Phrases

repeatedly replace numbersum of squares of digitsends in 1 or loops endlessly

NOT This Pattern When

Problems that require explicit graph traversal or DP without cycle detection.

Similar Problems

Linked List Cycle - same cycle detection techniqueFind the Duplicate Number - cycle detection in arrayDetect Cycle in a Graph - general cycle detection

Practice

1. You are given a circular array where each element represents the number of steps to move forward or backward. The goal is to determine if there exists a cycle where all moves are in the same direction and the cycle length is greater than 1. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Fast and slow pointer technique (Floyd's cycle detection) adapted for circular arrays with direction checks

B. Greedy approach that tries to jump as far as possible each time without revisiting indices

C. Dynamic programming to store reachable indices and cycle lengths

D. Brute force simulation with a visited set for each start index

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify algorithm that efficiently detects cycles

   Fast and slow pointer (Floyd's cycle detection) can detect cycles in O(n) time and O(1) space, with added direction checks to ensure cycle validity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast-slow pointer is classic for cycle detection in sequences [OK]

Hint: Cycle detection in sequences -> fast-slow pointer [OK]

Common Mistakes:

• Thinking greedy jumps detect cycles correctly
• Assuming DP applies here
• Using brute force is optimal

2. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

3. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

4. What is the time complexity of the fast and slow pointer algorithm for detecting a cycle in a linked list of length n?

medium

A. O(n) because the slow pointer traverses the list once and the fast pointer catches up quickly

B. O(n) because each node is visited at most twice by the pointers

C. O(n log n) due to repeated pointer comparisons

D. O(n^2) because the fast pointer moves twice as fast as the slow pointer

Solution

1. Step 1: Analyze pointer movements

   The slow pointer moves one step at a time, the fast pointer moves two steps. They meet within O(n) steps if a cycle exists.

2. Step 2: Confirm total steps taken

   Each node is visited at most twice by the pointers combined, so the total time complexity is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity confirmed by pointer meeting logic [OK]

Hint: Each node visited at most twice by pointers [OK]

Common Mistakes:

• Mistaking fast pointer speed as doubling complexity
• Assuming repeated comparisons cause log factor

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow