Happy Number (Digit Sum Cycle)

▶

Steps

setup

Initialize unhappy cycle set and start number

We define the set of known unhappy cycle numbers and initialize n with the input 19.

💡 This setup is crucial because the unhappy cycle set helps us detect loops that mean the number is not happy.

Line:

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

💡 The unhappy cycle set is a fixed known set that the algorithm uses to detect infinite loops.

compare

Check if n is 1 or in unhappy cycle

Check if the current number n=19 is 1 or in the unhappy cycle set to decide whether to continue.

💡 This check determines if we have reached a conclusion or need to continue transforming the number.

Line:

while n != 1 and n not in unhappy_cycle:

💡 Since 19 is neither 1 nor in the unhappy cycle, we proceed to compute the sum of squares of its digits.

fill_row

Extract digits of n to compute sum of squares

Start extracting digits from n=19 to compute the sum of their squares. Initialize total=0 and num=19.

💡 Extracting digits one by one is necessary to compute the sum of squares correctly.

Line:

total = 0
num = n

💡 We prepare to process each digit of the current number.

fill_cells

Extract last digit 9 and add its square

Extract the last digit 9 from num=19, square it (81), and add to total (total=81). Then reduce num by removing last digit (num=1).

💡 Processing each digit's square accumulates the sum needed to transform n.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Digit extraction and squaring is the core transformation step.

fill_cells

Extract last digit 1 and add its square

Extract the last digit 1 from num=1, square it (1), and add to total (total=82). Then reduce num to 0, ending digit extraction.

💡 Completing digit extraction finalizes the sum of squares for this iteration.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 All digits processed, total sum of squares is ready.

insert

Update n to sum of squares 82

Replace n with the computed sum of squares 82, preparing for the next iteration.

💡 Updating n is essential to continue the process with the new number.

Line:

n = digit_square_sum(n)

💡 The number transforms step by step towards 1 or an unhappy cycle.

compare

Check if n=82 is 1 or in unhappy cycle

Check if n=82 is 1 or in the unhappy cycle set to decide whether to continue.

💡 This check controls the loop continuation or termination.

Line:

while n != 1 and n not in unhappy_cycle:

💡 82 is neither 1 nor unhappy, so we continue transforming.

fill_cells

Compute sum of squares for n=82 digits

Extract digits 2 and 8 from 82, square and sum: 2²=4, 8²=64, total=68.

💡 Digit extraction and squaring repeats for each new number.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 The transformation continues stepwise.

fill_cells

Add square of digit 8 to total

Add 8²=64 to total=4, total becomes 68. Digit extraction ends as num reduces to 0.

💡 Completing digit processing yields the next number.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Sum of squares calculation is complete for this iteration.

insert

Update n to 68

Set n to 68, the sum of squares just computed, to continue the process.

💡 Updating n is essential to progress towards the final answer.

Line:

n = digit_square_sum(n)

💡 The number evolves stepwise through sum of squares.

compare

Check if n=68 is 1 or in unhappy cycle

Check if n=68 is 1 or in the unhappy cycle set to decide whether to continue.

💡 This check controls loop continuation.

Line:

while n != 1 and n not in unhappy_cycle:

💡 68 is neither 1 nor unhappy, so continue.

fill_cells

Compute sum of squares for n=68 digits

Extract digits 8 and 6 from 68, square and sum: 8²=64, 6²=36, total=100.

💡 Digit extraction and squaring repeats.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Transformation continues stepwise.

fill_cells

Add square of digit 6 to total

Add 6²=36 to total=64, total becomes 100. Digit extraction ends.

💡 Completing digit processing yields next number.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Sum of squares calculation complete for this iteration.

insert

Update n to 100

Set n to 100, the sum of squares just computed.

💡 Updating n is essential to continue.

Line:

n = digit_square_sum(n)

💡 Number evolves stepwise.

compare

Check if n=100 is 1 or in unhappy cycle

Check if n=100 is 1 or in the unhappy cycle set.

💡 Controls loop continuation.

Line:

while n != 1 and n not in unhappy_cycle:

💡 100 is neither 1 nor unhappy, continue.

fill_cells

Compute sum of squares for n=100 digits

Extract digits 0, 0, and 1 from 100, square and sum: 0²=0, 0²=0, 1²=1, total=1.

💡 Digit extraction and squaring repeats.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Transformation continues.

fill_cells

Add square of digit 0 to total

Add 0²=0 to total=0, continue digit extraction.

💡 Process all digits.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Sum remains 0 so far.

fill_cells

Add square of digit 1 to total

Add 1²=1 to total=0, total becomes 1. Digit extraction ends.

💡 Final digit processed completes sum.

Line:

digit = num % 10
 total += digit * digit
 num //= 10

💡 Sum of squares is 1, indicating happiness.

insert

Update n to 1

Set n to 1, the sum of squares just computed, which is the happy number condition.

💡 Updating n to 1 means the number is happy.

Line:

n = digit_square_sum(n)

💡 Reaching 1 means the number is happy and the loop will end.

prune

Return true because n is 1

Since n equals 1, the function returns true indicating the number 19 is happy.

💡 This final step confirms the algorithm's success.

Line:

return n == 1

💡 The algorithm terminates successfully when n reaches 1.

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

    def digit_square_sum(num: int) -> int:
        total = 0  # STEP 3
        while num > 0:  # STEP 4-5
            digit = num % 10  # STEP 4
            total += digit * digit  # STEP 4-5
            num //= 10  # STEP 4-5
        return total  # STEP 5

    while n != 1 and n not in unhappy_cycle:  # STEP 2,7,11,15
        n = digit_square_sum(n)  # STEP 6,10,14,19
    return n == 1  # STEP 20

📊

Happy Number (Digit Sum Cycle) - Watch the Algorithm Execute, Step by Step

Watching each transformation and decision helps you understand how the algorithm detects cycles and confirms happiness without guessing.

setup

n

1

0

9

1

compare

n

1

0

9

1

setup

n

1

0

num

9

1

Result: 0

fill_cells

n

1

0

num

9

1

Result: 81

fill_cells

n

1

0

9

1

Result: 82

insert

n

8

0

2

1

Result: 82

compare

n

8

0

2

1

Result: 82

fill_cells

n

8

0

num

2

1

Result: 4

fill_cells

n

8

0

2

1

Result: 68

insert

n

6

0

8

1

Result: 68

compare

n

6

0

8

1

Result: 68

fill_cells

n

6

0

num

8

1

Result: 64

fill_cells

n

6

0

8

1

Result: 100

insert

n

1

0

0

1

0

2

Result: 100

compare

n

1

0

0

1

0

2

Result: 100

fill_cells

n

1

0

0

1

num

0

2

Result: 0

fill_cells

n

1

0

num

0

1

0

2

Result: 0

fill_cells

n

1

0

0

1

0

2

Result: 1

insert

n

1

0

Result: 1

prune

n

1

0

Result: true

Key Takeaways

✓ The algorithm transforms the number by repeatedly summing the squares of its digits until it reaches 1 or a known unhappy cycle.

This iterative transformation is hard to visualize from code alone but becomes clear when watching each digit processed.

✓ Known unhappy cycle numbers allow the algorithm to detect infinite loops and stop early.

Understanding the role of this set is easier when you see the algorithm check membership at each iteration.

✓ Digit extraction and squaring is the core operation repeated every iteration, driving the number's evolution.

Seeing each digit extracted and squared step-by-step clarifies how the sum is computed.

Practice

1. Given an integer, determine if it reads the same backward as forward without converting it to a string. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the integer to a string and compare characters from both ends.

B. Use a greedy approach to compare digits from left to right until mismatch.

C. Reverse half of the integer digits and compare with the other half.

D. Use dynamic programming to store palindrome states of digit substrings.

Solution

1. Step 1: Understand the problem constraints

   We want to check if an integer is a palindrome without extra space and efficiently.

2. Step 2: Evaluate approaches

   Converting to string uses extra space; DP is overkill and not applicable; greedy fails on some cases. Reversing half the number uses O(1) space and O(log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reversing half the digits avoids overflow and extra space [OK]

Hint: Optimal uses half reversal, not full string conversion [OK]

Common Mistakes:

• Thinking string conversion is optimal
• Using DP unnecessarily
• Greedy fails on middle digits

2. 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

3. You need to reverse the digits of a 32-bit signed integer, returning 0 if the reversed integer overflows. Which approach guarantees an optimal solution that handles overflow correctly without converting the integer to a string?

easy

A. Greedy approach that swaps digits from ends until the middle is reached

B. Dynamic programming to store reversed prefixes and build the result

C. Brute force string conversion and reversal without overflow checks

D. Recursive digit extraction with overflow checks before each digit append

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing digits without string conversion and must handle overflow safely.

2. Step 2: Identify approach that meets constraints

   Recursive digit extraction with overflow checks ensures digits are reversed one by one and stops if overflow would occur, guaranteeing correctness and optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive digit extraction handles overflow and sign correctly [OK]

Hint: Overflow-safe digit extraction is key [OK]

Common Mistakes:

• Using string reversal without overflow checks
• Greedy swaps fail on overflow
• DP is unnecessary overhead

4. What is the time complexity of the optimal approach that uses a hash set and checks pairs of points as diagonals to find the minimum area rectangle, given n points?

medium

A. O(n^4) because all quadruples of points are checked

B. O(n^2) because all pairs of points are checked and hash set lookups are O(1)

C. O(n^3) because for each pair, a linear search is done for complementary points

D. O(n log n) because points are sorted and then pairs are checked

Solution

1. Step 1: Identify loops in the optimal approach

   The code iterates over all pairs of points (i,j), which is O(n^2).

2. Step 2: Analyze point existence checks

   Checking if complementary points exist uses a hash set with O(1) average lookup, so no extra multiplicative factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Double loop + O(1) lookup -> O(n^2) time [OK]

Hint: Pairs checked, hash lookups O(1) -> O(n^2) [OK]

Common Mistakes:

• Confusing with brute force O(n^4)
• Assuming linear search inside pairs causes O(n^3)

5. Consider the following buggy code for Roman to Integer conversion. Which line contains the subtle bug that causes incorrect results for inputs like "IV" or "IX"?

medium

A. Line with 'result += curr'

B. Line with 'next_val = value(s[i + 1]) if i + 1 < len(s) else 0'

C. Line with 'curr = value(s[i])'

D. Line with 'if curr <= next_val:'

Solution

1. Step 1: Identify the condition for subtraction

   The correct condition is to subtract only when current value is strictly less than next value, not when equal.

2. Step 2: Analyze the buggy condition

   The code uses 'if curr <= next_val:', which incorrectly subtracts when values are equal, causing wrong results for cases like 'IV' or 'IX'.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing '<=' to '<' fixes the bug [OK]

Hint: Subtraction only if current < next, not <= [OK]

Common Mistakes:

• Using <= instead of <
• Forgetting boundary checks
• Wrong value mappings