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 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 for the optimal Insert Delete GetRandom data structure. After executing the code below, what is the content of the list nums and the dictionary pos?

rs = RandomizedSet()
rs.insert(1)
rs.insert(2)
rs.insert(3)
rs.remove(2)

easy

A. nums = [3, 1], pos = {3: 0, 1: 1}

B. nums = [1, 2, 3], pos = {1: 0, 2: 1, 3: 2}

C. nums = [1], pos = {1: 0}

D. nums = [1, 3], pos = {1: 0, 3: 1}

Solution

1. Step 1: Trace insertions

   Insert 1 -> nums=[1], pos={1:0}; Insert 2 -> nums=[1,2], pos={1:0,2:1}; Insert 3 -> nums=[1,2,3], pos={1:0,2:1,3:2}

2. Step 2: Trace removal of 2

   Remove 2 at idx=1; last_element=3; swap nums[1]=3; update pos[3]=1; pop last element; delete pos[2]; final nums=[1,3], pos={1:0,3:1}

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap-delete updates indices correctly [OK]

Hint: Swap last element with removed index to keep O(1) [OK]

Common Mistakes:

• Forgetting to update pos after swap
• Not swapping and popping, causing O(n) remove
• Assuming elements remain in insertion order

3. Consider the following buggy code for finding the first unique character index. Which line contains the subtle bug that causes incorrect results when duplicates are non-adjacent?

def firstUniqChar(s: str) -> int:
    freq = {}
    for i, ch in enumerate(s):
        if ch not in freq:
            freq[ch] = 1
        else:
            freq[ch] += 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return ch
    return -1

medium

A. Line 9: returning the character instead of its index

B. Line 3: initializing frequency dictionary incorrectly

C. Line 7: incrementing frequency count incorrectly

D. Line 11: returning -1 instead of 0 when no unique character

Solution

1. Step 1: Analyze return statement in second loop

   The code returns the character itself instead of its index, violating problem requirements.

2. Step 2: Confirm other lines are correct

   Frequency counting and increments are correct; returning -1 when no unique char is standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Return value must be index, not character [OK]

Hint: Return index, not character [OK]

Common Mistakes:

• Returning character instead of index
• Not handling no unique char case
• Incorrect frequency updates

4. Suppose the data structure must support duplicate elements (i.e., multiple identical values can be inserted). Which modification to the optimal Insert Delete GetRandom design correctly supports duplicates while maintaining average O(1) insert, remove, and getRandom?

hard

A. Use a hash map from value to a set of indices in the array, update sets on insert and remove, and swap-delete as before

B. Store counts of each value in a hash map and keep a list of unique values only, ignoring duplicates in the array

C. Use a linked list instead of an array to store elements and a hash map for counts

D. Disallow duplicates by checking presence before insert, same as original design

Solution

1. Step 1: Understand duplicate challenge

   Duplicates mean one value maps to multiple indices; a single index in pos is insufficient.

2. Step 2: Modify data structures

   Use a hash map from value to a set of indices to track all positions; update sets on insert/remove; swap-delete still works by updating sets accordingly.

3. Step 3: Verify O(1) operations

   Set insert/remove are O(1) average; array swap-delete remains O(1); getRandom picks random index from array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value enables duplicates with O(1) ops [OK]

Hint: Map values to sets of indices to handle duplicates [OK]

Common Mistakes:

• Using counts only loses position info
• Ignoring duplicates breaks getRandom correctness
• Using linked list loses O(1) random access

5. Suppose the input array can contain duplicate numbers and you want to find the longest consecutive sequence length allowing repeated elements to be counted only once. Which modification to the optimal hash set approach correctly handles duplicates without inflating the sequence length?

hard

A. Sort the array and count consecutive numbers, skipping duplicates during the scan.

B. Use the hash set approach but iterate over the original array instead of the set.

C. Use a hash map to count frequencies and multiply sequence length by frequency.

D. Use the hash set approach as is, since duplicates are automatically ignored by the set.

Solution

1. Step 1: Understand duplicate impact

   Duplicates can inflate counts if not handled properly.

2. Step 2: Evaluate modifications

   Iterating over original array or multiplying by frequency inflates length. Using set alone ignores duplicates but does not handle sorted consecutive counting with duplicates properly.

3. Step 3: Correct approach

   Sorting and skipping duplicates during linear scan correctly counts longest consecutive sequence without inflating length.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + skipping duplicates ensures correct consecutive count [OK]

Hint: Sorting + skip duplicates handles repeated elements correctly [OK]

Common Mistakes:

• Iterating over original array causing duplicates counted multiple times
• Multiplying length by frequency inflates result
• Assuming set alone handles duplicates correctly