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 an array of integers and need to determine if any value appears at least twice. Which approach guarantees the most efficient detection of duplicates in terms of time complexity?

easy

A. Sort the array and then scan once to check if any adjacent elements are equal.

B. Use a hash set to track seen elements and check membership while iterating once.

C. Use nested loops to compare every pair of elements for equality.

D. Use dynamic programming to build a table of duplicate occurrences.

Solution

1. Step 1: Understand the problem requirements

   The problem requires detecting duplicates efficiently in an array.

2. Step 2: Compare approaches based on time complexity

   Sorting then scanning is O(n log n), nested loops is O(n²), and dynamic programming is unnecessary here. Using a hash set allows O(n) time with O(n) space by checking membership during one pass.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set membership check is O(1) average, enabling linear time detection [OK]

Hint: Hash set membership check enables linear time detection [OK]

Common Mistakes:

• Confusing sorting approach as optimal
• Thinking nested loops are efficient enough
• Misapplying DP to a membership problem

2. Consider the following Python code implementing the optimal bucket sort approach for top K frequent elements. What is the value of res just before the function returns when called with nums = [1,2,2,3] and k = 2?

easy

A. [1, 2]

B. [2, 1]

C. [2, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequency map for nums=[1,2,2,3]

   freq = {1:1, 2:2, 3:1}, max_freq = 2

2. Step 2: Fill buckets and collect top k=2 elements

   buckets = [[], [1,3], [2]]; iterate from freq=2 down: add 2, then freq=1 add 1; res = [2,1]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order depends on bucket insertion; here 2 appears before 1 [OK]

Hint: Trace buckets from highest frequency down [OK]

Common Mistakes:

• Confusing order of elements in buckets
• Assuming sorted order inside buckets
• Off-by-one in frequency indexing

3. Identify the bug in the following code snippet for grouping anagrams:

medium

A. Line 4: defaultdict initialization

B. Line 7: Incrementing count array

C. Line 10: Appending string to map

D. Line 9: Using ''.join(count) to create key

Solution

1. Step 1: Understand key creation

   Count is a list of integers; ''.join(count) tries to join integers as strings, causing TypeError or incorrect keys.

2. Step 2: Correct key creation

   Key should be a tuple of counts to be hashable and unique, e.g., key = tuple(count).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using ''.join on int list causes errors or wrong grouping [OK]

Hint: Keys must be hashable types like tuples, not joined strings of ints [OK]

Common Mistakes:

• Joining int list without conversion
• Using list as dict key
• Forgetting to convert count to tuple

4. The following code attempts to find the longest subarray with sum divisible by k. Identify the line containing the subtle bug that causes incorrect results for arrays containing negative numbers.

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        # Bug: missing adjustment for negative remainder
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

medium

A. Line computing remainder = prefix_sum % k

B. Line initializing earliest[0] = -1

C. Line updating max_length = max(max_length, i - earliest[remainder])

D. Line setting earliest[remainder] = i

Solution

1. Step 1: Identify remainder calculation

   When prefix_sum is negative, prefix_sum % k in Python returns a non-negative remainder, but in some languages or implementations it can be negative. The code lacks adjustment for negative remainder.

2. Step 2: Why this causes bugs

   If remainder is negative, indexing earliest array causes errors or misses correct subarrays. The fix is to add if remainder < 0: remainder += k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Negative prefix sums require remainder adjustment [OK]

Hint: Check remainder calculation for negative sums [OK]

Common Mistakes:

• Forgetting to adjust negative remainders
• Misinitializing earliest array
• Updating max_length incorrectly

5. Suppose the input strings can contain uppercase letters and digits in addition to lowercase letters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a frequency array of size 62 (26 lowercase + 26 uppercase + 10 digits) and map characters accordingly.

B. Use a frequency array of size 26 and convert all characters to lowercase before counting.

C. Sort each string and use the sorted string as the hash map key.

D. Use a hash map with character counts stored as a dictionary instead of an array.

Solution

1. Step 1: Identify character set

   Input includes lowercase, uppercase, and digits, total 62 distinct characters.

2. Step 2: Adjust frequency counting

   Frequency array size must be 62, mapping each character to an index to count correctly.

3. Step 3: Evaluate alternatives

   Converting to lowercase loses information, sorting is slower, dictionary counts add overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency array size matches character set size [OK]

Hint: Frequency array size must cover all possible characters [OK]

Common Mistakes:

• Lowercasing loses info
• Using smaller array size
• Assuming sorting is always best