Happy Number (Digit Sum Cycle)

📋

Problem

Imagine a game where you repeatedly replace a number by the sum of the squares of its digits. Some numbers eventually reach 1 and are called 'happy', while others get stuck in a loop. Can you determine if a number is happy?

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 that does not include 1. Return true if n is a happy number, and false otherwise.

1 ≤ n ≤ 10^5

Edge cases: 1 → true (smallest happy number)7 → true (happy number with short cycle to 1)0 → false (not positive, but test robustness)

</>

IDE

def isHappy(n: int) -> bool:public boolean isHappy(int n)bool isHappy(int n)function isHappy(n)

def isHappy(n: int) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isHappy(int n) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isHappy(int n) {
    // Write your solution here
    return false;
}

function isHappy(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for input 2Missing cycle detection causes infinite loop or incorrect true return.✅ Implement a set or Floyd's cycle detection to detect cycles and return false if cycle detected.

Wrong: false for input 1Missing base case for n == 1 causes incorrect false return.✅ Add a direct check: if n == 1 return true immediately.

Wrong: true for input 0No input validation for zero or non-positive numbers.✅ Add input validation to return false if n < 1.

Wrong: TLE on large input 100000Inefficient cycle detection storing all seen numbers causes time limit exceeded.✅ Use Floyd's cycle detection algorithm to detect cycles in O(1) space and avoid TLE.

Wrong: true for input 4Greedy or premature termination before confirming cycle causes incorrect true.✅ Fully iterate until 1 or cycle detected using proper cycle detection.

✓

Test Cases

Focus on handling boundary cases like zero and the smallest happy number.

Watch out for common pitfalls like greedy early stopping and cycle detection errors.

Optimize your solution to run efficiently on large inputs using constant space cycle detection.

t1_01basic

Input{"n":19}

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Try simulating the sum of squares of digits repeatedly.

💡 Use a set to detect cycles or check if number reaches 1.

💡 Return true if 1 is reached; otherwise false if a cycle is detected.

Why it failed: Failed on canonical example: likely missing cycle detection or incorrect digit square sum calculation. Fix by implementing cycle detection with a set and correct digit extraction.

✓ Correctly detects happy numbers using cycle detection and digit square sums.

t1_02basic

Input{"n":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle without 1), so 2 is not happy.

💡 Check if the sequence enters a cycle without reaching 1.

💡 Use a set to track seen numbers to detect cycles.

💡 Return false if a previously seen number repeats before reaching 1.

Why it failed: Incorrectly returns true for a non-happy number due to missing cycle detection. Fix by storing seen numbers and returning false upon repetition.

✓ Correctly identifies non-happy numbers by detecting cycles.

t2_01edge

Input{"n":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

0 is not positive and does not reach 1; should return false.

💡 Check how your code handles zero or non-positive inputs.

💡 Ensure input validation or handle zero as a special case.

💡 Return false immediately if n is less than 1.

Why it failed: Returns true or crashes on zero input due to lack of input validation. Fix by adding a check to return false if n < 1.

✓ Properly handles zero input by returning false.

t2_02edge

Input{"n":1}

Expectedtrue

⏱ Performance - must finish in 2000ms

1 is the smallest happy number by definition.

💡 Check if your code correctly returns true immediately for input 1.

💡 Recognize 1 as the base case for happiness.

💡 Return true if n == 1 without further processing.

Why it failed: Fails to return true for input 1, possibly due to missing base case. Fix by adding a direct check for n == 1.

✓ Correctly returns true for input 1.

t2_03edge

Input{"n":100000}

Expectedtrue

⏱ Performance - must finish in 2000ms

100000 → 1²+0+0+0+0+0=1, so 100000 is happy.

💡 Test large inputs near constraint boundary.

💡 Ensure digit extraction and sum calculation handle multiple zeros correctly.

💡 Return true if sum of squares leads to 1.

Why it failed: Fails on large input due to incorrect digit sum or overflow. Fix by correctly summing squares of all digits including zeros.

✓ Handles large inputs correctly and returns true when appropriate.

t3_01corner

Input{"n":7}

Expectedtrue

⏱ Performance - must finish in 2000ms

7 → 49 → 97 → 130 → 10 → 1, so 7 is happy with a short cycle to 1.

💡 Beware of greedy approaches that stop early without full cycle detection.

💡 Use cycle detection to confirm eventual reach of 1.

💡 Implement Floyd's cycle detection or a set to detect cycles properly.

Why it failed: Fails due to greedy early termination before confirming 1 is reached. Fix by fully iterating until 1 or cycle detected.

✓ Correctly handles numbers with short cycles to 1.

t3_02corner

Input{"n":4}

Expectedfalse

⏱ Performance - must finish in 2000ms

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (cycle without 1), so 4 is not happy.

💡 Avoid confusing 0/1 constraints; this is a 0/1 problem with cycle detection.

💡 Ensure cycle detection is implemented, not just a fixed iteration count.

💡 Return false if cycle detected without reaching 1.

Why it failed: Fails by confusing problem constraints or missing cycle detection, returning incorrect true. Fix by implementing proper cycle detection.

✓ Correctly identifies non-happy numbers with cycles.

t3_03corner

Input{"n":3}

Expectedfalse

⏱ Performance - must finish in 2000ms

3 → 9 → 81 → 65 → 61 → 37 → ... cycle without 1, so 3 is not happy.

💡 Check for off-by-one errors in loop or cycle detection.

💡 Ensure all intermediate sums are checked against seen numbers.

💡 Use a loop that continues until 1 or repeated number is found.

Why it failed: Fails due to off-by-one error causing premature termination or missed cycle detection. Fix by checking cycle condition after updating number.

✓ Correctly detects cycles and returns false for unhappy numbers.

t4_01performance

Input{"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=100000 at constraint boundary; solution must run in O(k * log n) time within 2 seconds.

💡 Use Floyd's cycle detection to reduce space complexity.

💡 Avoid storing all seen numbers to save memory.

💡 Optimize digit square sum calculation for speed.

Why it failed: TLE due to exponential or inefficient cycle detection (e.g., storing all seen numbers). Fix by implementing Floyd's cycle detection with O(1) space.

✓ Efficient cycle detection confirms O(k * log n) complexity and passes performance test.

Practice

1. Consider the following code snippet that checks if a number is a palindrome by reversing half of its digits. What is the value of reversed_half after the second iteration of the while loop when input is 12321?

easy

A. 12

B. 1

C. 21

D. 123

Solution

1. Step 1: Trace first iteration

   Initial x=12321, reversed_half=0 reversed_half = 0*10 + 12321%10 = 1 x = 12321 // 10 = 1232

2. Step 2: Trace second iteration

   reversed_half = 1*10 + 1232%10 = 10 + 2 = 12 x = 1232 // 10 = 123

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After two iterations reversed_half is 12 [OK]

Hint: Track variable updates carefully each loop iteration [OK]

Common Mistakes:

• Off-by-one iteration count
• Mixing x and reversed_half values
• Incorrect modulo or division

2. Given the following Python code to find the nth ugly number, what is the output when calling nthUglyNumber(4)?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = {1}
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

print(nthUglyNumber(4))

easy

A. 6

B. 5

C. 8

D. 4

Solution

1. Step 1: Trace heap pops and pushes for n=4

   Initial heap: [1]. Iteration 1 pops 1, pushes 2,3,5. Iteration 2 pops 2, pushes 4,6,10. Iteration 3 pops 3, pushes 6 (already seen), 9, 15. Iteration 4 pops 4, pushes 8,12,20.

2. Step 2: Identify the 4th popped ugly number

   The popped numbers in order are 1, 2, 3, 4. The 4th ugly number is 4, so nthUglyNumber(4) returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   4 is the 4th ugly number generated by the heap [OK]

Hint: Heap pops nth ugly number in ascending order [OK]

Common Mistakes:

• Confusing the iteration count with the returned value
• Forgetting duplicates are skipped
• Miscounting the order of popped elements

3. What is the time complexity of the optimal palindrome number check algorithm that reverses half of the digits, and why?

medium

A. O(log n), where n is the integer value, because the number of digits is proportional to log base 10 of n.

B. O(n), where n is the number of digits, because it processes each digit once.

C. O(n^2), because reversing digits involves nested operations on each digit.

D. O(1), because it only reverses half the digits regardless of input size.

Solution

1. Step 1: Identify input size parameter

   Input is an integer n; number of digits d = floor(log10(n)) + 1.

2. Step 2: Analyze loop iterations

   The loop runs until reversed_half >= x, roughly half the digits processed -> O(d).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time depends on digit count, which is linear in number of digits [OK]

Hint: Time depends on digit count, not numeric value directly [OK]

Common Mistakes:

• Confusing n as digit count vs integer value
• Assuming O(1) due to half reversal
• Mistaking nested loops cause O(n^2)

4. What is the time complexity of the min-heap based algorithm to find the nth ugly number, and why might a common misconception about it be incorrect?

medium

A. O(n^2) because each number can generate up to 3 new numbers leading to quadratic growth.

B. O(n) because each number is processed exactly once without duplicates.

C. O(n log n) because each of the n iterations involves popping and pushing in a heap of size up to n.

D. O(n log k) where k is the number of unique ugly numbers generated, which is less than n.

Solution

1. Step 1: Identify operations per iteration

   Each iteration pops one element from the heap and pushes up to 3 new elements if unseen.

2. Step 2: Analyze heap size and operations

   The heap size can grow up to O(n) because duplicates are avoided. Each push/pop operation costs O(log n), so total time is O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate complexity, confirming O(n log n) [OK]

Hint: Heap push/pop cost dominates, not just number of elements [OK]

Common Mistakes:

• Assuming linear time because each number is processed once
• Thinking complexity is quadratic due to multiple pushes per iteration
• Confusing k (unique numbers) with n (iterations)

5. Suppose the Excel column titles can now include lowercase letters (a-z) in addition to uppercase (A-Z), where 'a' corresponds to 1 and 'z' to 26, independent of uppercase letters. How should the algorithm be modified to correctly convert such titles to numbers?

hard

A. Convert all letters to uppercase and use existing logic

B. Treat uppercase letters as base-26 digits and lowercase letters as separate base-26 digits, then sum

C. Use a combined mapping where 'A'-'Z' and 'a'-'z' both map to 1-26, then apply base-26 logic

D. Map uppercase and lowercase letters separately to 1-26 and multiply by 52 instead of 26

Solution

1. Step 1: Understand the new character set

   Now there are 52 possible characters (A-Z and a-z), each mapping to 1-26 independently.

2. Step 2: Adjust base and mapping accordingly

   Since there are 52 distinct characters, the base must be 52, and mapping must distinguish uppercase and lowercase letters.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base must match character set size; 26 is insufficient for mixed case [OK]

Hint: Base equals number of distinct characters [OK]

Common Mistakes:

• Ignoring case difference
• Using base 26 for 52 chars
• Mapping lowercase to same as uppercase