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. You are given a circular array where each element represents a jump length and direction (positive for forward, negative for backward). The task is to determine if there exists a cycle in the array such that the cycle is longer than one element and all jumps are in the same direction. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to jump as far as possible from each index until a cycle is detected or no progress is made.

B. Dynamic programming to store reachable indices and detect cycles by memoization.

C. Brute force simulation from each index checking all possible cycles exhaustively.

D. Fast and slow pointer cycle detection that checks direction consistency and avoids single-element loops.

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 suitable algorithm

   Fast and slow pointer cycle detection efficiently finds cycles in O(n) time while checking direction and cycle length constraints.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast and slow pointers detect cycles without exhaustive search [OK]

Hint: Cycle detection with direction check -> fast-slow pointers [OK]

Common Mistakes:

• Assuming greedy jumps always find cycles
• Using DP which is inefficient here
• Brute force is correct but not optimal

2. Identify the bug in the following code snippet for finding the duplicate number using Floyd's cycle detection:

medium

A. The initialization of slow and fast pointers is incorrect

B. The second while loop incorrectly updates fast pointer

C. The first while loop condition causes an infinite loop

D. The return statement should return fast instead of slow

Solution

1. Step 1: Examine the first while loop condition

   The loop condition is while slow != fast, but slow and fast are initialized to the same value, so the loop never runs, causing no intersection point found.

2. Step 2: Understand consequences

   Without the loop running, slow and fast pointers do not move, so the algorithm fails to detect the cycle and returns incorrect result or loops infinitely if code is modified.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop condition must allow first iteration; using while True with break is correct [OK]

Hint: First loop must run at least once to find intersection [OK]

Common Mistakes:

• Using while slow != fast before pointers move
• Incorrect pointer updates inside loops
• Returning wrong pointer at the end

3. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

4. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily