Happy Number

▶

Steps

setup

Initialize cycle set and start number

The algorithm initializes the set of known cycle numbers that indicate unhappy sequences. The starting number is set to 19.

💡 This setup defines the stopping conditions: reaching 1 means happy, reaching any cycle number means unhappy.

Line:

cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}
n = 19

💡 The cycle set is a fixed known set of numbers that cause infinite loops if the sequence reaches them.

compare

Check if current number is 1 or in cycle set

The algorithm checks if the current number 19 is 1 or in the cycle set. It is neither, so the algorithm proceeds to compute the next number.

💡 This check determines if the algorithm can stop early or must continue iterating.

Line:

while n != 1 and n not in cycle_set:

💡 The algorithm only stops if the number is 1 (happy) or in the cycle set (unhappy).

fill_cells

Compute next number from 19

Calculate the sum of squares of digits of 19: 1² + 9² = 1 + 81 = 82. The next number is 82.

💡 This transformation generates the next number in the sequence to check.

Line:

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

n = get_next(n)

💡 The sum of squares of digits function transforms the current number into the next number in the sequence.

compare

Check if current number 82 is 1 or in cycle set

Check if 82 is 1 or in the cycle set. It is neither, so continue iterating.

💡 Each iteration must verify if the sequence has reached a stopping condition.

Line:

while n != 1 and n not in cycle_set:

💡 The algorithm continues until it finds 1 or a cycle number.

fill_cells

Compute next number from 82

Calculate sum of squares of digits of 82: 8² + 2² = 64 + 4 = 68. The next number is 68.

💡 This step continues the sequence generation by transforming the current number.

Line:

n = get_next(n)

💡 The sequence progresses by repeatedly applying the sum of squares function.

compare

Check if current number 68 is 1 or in cycle set

Check if 68 is 1 or in the cycle set. It is neither, so continue iterating.

💡 The algorithm must verify the stopping condition at each step.

Line:

while n != 1 and n not in cycle_set:

💡 The loop continues until a terminal condition is met.

fill_cells

Compute next number from 68

Calculate sum of squares of digits of 68: 6² + 8² = 36 + 64 = 100. The next number is 100.

💡 The sequence continues transforming numbers until it reaches a stopping condition.

Line:

n = get_next(n)

💡 The sum of squares function can produce numbers with fewer digits, like 100 here.

compare

Check if current number 100 is 1 or in cycle set

Check if 100 is 1 or in the cycle set. It is neither, so continue iterating.

💡 The algorithm checks the stopping condition at every iteration.

Line:

while n != 1 and n not in cycle_set:

💡 The loop continues as long as the number is not 1 or in the cycle set.

fill_cells

Compute next number from 100

Calculate sum of squares of digits of 100: 1² + 0² + 0² = 1 + 0 + 0 = 1. The next number is 1.

💡 This step reaches the happy number 1, which means the sequence will terminate successfully.

Line:

n = get_next(n)

💡 Reaching 1 means the original number is happy and the algorithm will return true.

compare

Check if current number 1 is 1 or in cycle set

Check if 1 is 1 or in the cycle set. It is 1, so the algorithm will terminate and return true.

💡 This final check confirms the number is happy and ends the loop.

Line:

while n != 1 and n not in cycle_set:

💡 The algorithm terminates successfully when the sequence reaches 1.

reconstruct

Return result true for happy number

The algorithm returns true because the sequence reached 1, confirming 19 is a happy number.

💡 This final step outputs the result of the algorithm after all iterations.

Line:

return n == 1

💡 The final output depends on whether the sequence ended at 1 or a cycle number.

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

    def get_next(number):  # STEP 3,5,7,9
        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:  # STEP 2,4,6,8,10
        n = get_next(n)  # STEP 3,5,7,9
    return n == 1  # STEP 11

📊

Happy Number - Watch the Algorithm Execute, Step by Step

Watching each transformation and check step-by-step reveals how the algorithm detects cycles and terminates correctly, which is hard to grasp from code alone.

setup

19

compare

19

fill_cells

19

→

82

compare

19

→

82

fill_cells

19

→

82

→

68

compare

19

→

82

→

68

fill_cells

19

→

82

→

68

→

100

compare

19

→

82

→

68

→

100

fill_cells

19

→

82

→

68

→

100

→

1

compare

19

→

82

→

68

→

100

→

1

Result: true

reconstruct

19

→

82

→

68

→

100

→

1

Result: true

Key Takeaways

✓ The algorithm detects happy numbers by iterating through a sequence generated by summing squares of digits until it reaches 1 or a known cycle.

This insight is hard to see from code alone because the sequence and cycle detection are implicit and require following the transformations step-by-step.

✓ The known cycle set acts as a fast cycle detection mechanism to prevent infinite loops in unhappy numbers.

Understanding the role of the cycle set is easier when you see the algorithm check membership at each step visually.

✓ Each step transforms the current number into the next, showing how the sequence evolves and why the algorithm terminates.

Watching each sum of squares calculation clarifies how the sequence progresses, which is abstract in code.

Practice

1. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

2. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

3. Consider the following buggy code snippet for splitting a linked list into k parts. Which line contains the subtle bug that can cause parts to remain connected, leading to incorrect output or infinite loops?

medium

A. Line where current.next is set to null (missing in this code)

B. Line where parts[i] is assigned

C. Line where remainder is decremented

D. Line where total_nodes is counted

Solution

1. Step 1: Identify missing link break

   The code comments out the lines that break the link after each part, so parts remain connected.

2. Step 2: Understand impact

   Without setting current.next = null, parts share nodes, causing incorrect output or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Breaking links is essential to separate parts [OK]

Hint: Always break links to separate parts [OK]

Common Mistakes:

• Forgetting to break links
• Misplacing remainder decrement
• Incorrectly assigning parts[i]

4. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods

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