Reverse Integer

▶

Steps

setup

Initialize variables and sign

Determine the sign of the input and convert it to a positive number for processing.

💡 Separating sign simplifies reversing digits without sign complications.

Line:

sign = -1 if x < 0 else 1
x = abs(x)

💡 Sign handling is separated from digit reversal to simplify logic.

setup

Enter helper recursion with initial values

Call helper function with num = 123 and rev = 0 to start reversing digits.

💡 Helper function manages recursion and accumulator for reversed number.

Line:

def helper(num, rev):
    if num == 0:
        return rev
    ...
rev = helper(x, 0)

💡 Initial call sets the stage for recursive digit extraction and accumulation.

fill_cells

Extract last digit (pop) from num

Calculate pop = num % 10 to get the last digit 3 from 123.

💡 Extracting the last digit is the core step to reverse digits one by one.

Line:

pop = num % 10

💡 Modulo operation isolates the last digit for reversal.

compare

Check for overflow before appending digit

Verify if rev * 10 + pop would overflow 32-bit integer limits.

💡 Preventing overflow is critical to avoid invalid reversed integers.

Line:

if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
    return 0

💡 Overflow check ensures safe integer reversal within bounds.

traverse

Recurse with num // 10 and updated rev

Call helper with num = 12 and rev = 0 * 10 + 3 = 3 to continue reversal.

💡 Recursion moves to next digit by reducing num and growing rev.

Line:

return helper(num // 10, rev * 10 + pop)

💡 Recursive call advances digit reversal step-by-step.

fill_cells

Extract last digit (pop) from num = 12

Calculate pop = 12 % 10 = 2 to extract next digit.

💡 Extracting next digit continues reversal process.

Line:

pop = num % 10

💡 Each recursive call extracts one digit from num.

compare

Check for overflow before appending digit

Check if rev * 10 + pop = 3 * 10 + 2 = 32 would overflow.

💡 Overflow check repeated at each step to ensure safety.

Line:

if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
    return 0

💡 Overflow condition not met, safe to proceed.

traverse

Recurse with num // 10 and updated rev

Call helper with num = 1 and rev = 3 * 10 + 2 = 32.

💡 Recursion continues to next digit.

Line:

return helper(num // 10, rev * 10 + pop)

💡 Accumulator rev grows as digits append.

fill_cells

Extract last digit (pop) from num = 1

Calculate pop = 1 % 10 = 1 to extract last digit.

💡 Final digit extraction before base case.

Line:

pop = num % 10

💡 Last digit extracted for final append.

compare

Check for overflow before appending digit

Check if rev * 10 + pop = 32 * 10 + 1 = 321 would overflow.

💡 Final overflow check before completing reversal.

Line:

if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
    return 0

💡 Final digit append is safe within 32-bit integer range.

traverse

Recurse with num // 10 and updated rev

Call helper with num = 0 and rev = 321 to reach base case.

💡 Recursion moves to base case where num is zero.

Line:

return helper(num // 10, rev * 10 + pop)

💡 Base case will return the fully reversed number.

prune

Base case reached: num == 0

Return rev = 321 as the reversed integer since num is zero.

💡 Base case ends recursion and returns the result.

Line:

if num == 0:
    return rev

💡 Recursion unwinds returning the reversed number.

reconstruct

Apply original sign to reversed integer

Multiply reversed number by sign to restore original sign (positive here).

💡 Sign restoration completes the reversal process.

Line:

return sign * rev if rev != 0 else 0

💡 Final output respects original input sign.

reconstruct

Final reversed integer ready

The reversed integer 321 is returned as the final answer.

💡 This is the output of the entire reversal algorithm.

Line:

return sign * rev if rev != 0 else 0

💡 Reversal complete and result fits in 32-bit integer range.

def reverse(x: int) -> int:
    INT_MAX = 2**31 - 1  # STEP 1
    INT_MIN = -2**31
    sign = -1 if x < 0 else 1  # STEP 1
    x = abs(x)  # STEP 1

    def helper(num, rev):  # STEP 2
        if num == 0:  # STEP 12
            return rev
        pop = num % 10  # STEP 3,6,9
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):  # STEP 4,7,10
            return 0
        return helper(num // 10, rev * 10 + pop)  # STEP 5,8,11

    rev = helper(x, 0)  # STEP 2
    return sign * rev if rev != 0 else 0  # STEP 13,14

📊

Reverse Integer - Watch the Algorithm Execute, Step by Step

Watching each digit extraction and accumulation step reveals how the algorithm builds the reversed integer safely and efficiently.

setup

x

1

0

2

1

3

2

Result: 0

setup

rev

1

0

2

1

3

2

Result: 0

fill_cells

rev

1

0

2

1

pop

3

2

Result: 0

compare

rev

1

0

2

1

pop

3

2

Result: 0

traverse

rev

1

0

2

1

Result: 3

fill_cells

rev

1

0

pop

2

1

Result: 3

compare

rev

1

0

pop

2

1

Result: 3

traverse

rev

1

0

Result: 32

fill_cells

rev

1

0

Result: 32

compare

pop

1

0

Result: 32

traverse

Result: 321

prune

Result: 321

reconstruct

Result: 321

record

Result: 321

Key Takeaways

✓ Digit extraction and accumulation happen recursively, building the reversed integer one digit at a time.

This stepwise recursion is clearer visually than reading code, which can obscure the flow.

✓ Overflow checks at each step prevent invalid reversed integers beyond 32-bit limits.

Seeing the check before each append clarifies why some inputs return 0.

✓ Separating sign handling from digit reversal simplifies the logic and avoids sign-related bugs.

Visualizing sign as a separate pointer helps understand why reversal works on absolute values.

Practice

1. You need to find the smallest positive number that is divisible by two given integers, and also find the greatest integer that divides both. Which approach guarantees the most efficient and reliable solution for this problem?

easy

A. Use a brute force search checking multiples and divisors until the answer is found.

B. Use a greedy algorithm that picks the largest divisor first and tries to build the LCM.

C. Apply the Euclidean algorithm iteratively to find GCD, then compute LCM using the GCD.

D. Use dynamic programming to store intermediate divisors and multiples for both numbers.

Solution

1. Step 1: Understand the problem requirements

   The problem requires finding the greatest common divisor (GCD) and least common multiple (LCM) of two integers efficiently.

2. Step 2: Evaluate approaches

   Brute force is inefficient for large inputs. Dynamic programming and greedy approaches do not naturally fit this problem. The Euclidean algorithm efficiently computes GCD in O(log(min(a,b))) time, and LCM can be derived from GCD.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Euclidean algorithm is the standard optimal method for GCD and LCM [OK]

Hint: Euclidean algorithm efficiently finds GCD and LCM [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing greedy with Euclidean algorithm

2. Consider the following Python code that computes GCD and LCM of two numbers:

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm_safe(a, b):
    gcd = gcd_iterative(a, b)
    return a // gcd * b

if __name__ == '__main__':
    a, b = 8, 12
    gcd = gcd_iterative(a, b)
    lcm = lcm_safe(a, b)
    print("GCD =", gcd)
    print("LCM =", lcm)

What is the output of this program?

easy

A. GCD = 4
LCM = 24

B. GCD = 2
LCM = 48

C. GCD = 4
LCM = 96

D. GCD = 8
LCM = 12

Solution

1. Step 1: Trace gcd_iterative(8, 12)

   Initial: a=8, b=12 Iteration 1: a=12, b=8%12=8 Iteration 2: a=8, b=12%8=4 Iteration 3: a=4, b=8%4=0 Return gcd=4

2. Step 2: Compute lcm_safe(8, 12)

   lcm = (8 // 4) * 12 = 2 * 12 = 24

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   GCD(8,12)=4 and LCM(8,12)=24 [OK]

Hint: GCD divides both numbers; LCM is product divided by GCD [OK]

Common Mistakes:

• Confusing order of modulo in Euclidean algorithm
• Calculating LCM as a*b without dividing by GCD

3. The following code attempts to determine if a number is happy but contains a subtle bug. Identify the line with the bug.

def isHappy(n: int) -> bool:
    def digit_square_sum(num: int) -> int:
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    while n != 1:
        n = digit_square_sum(n)
    return True

medium

A. Line with 'while n != 1:' loop condition

B. Missing cycle detection causing infinite loop

C. Line with 'return True' after the loop

D. Line with 'n = digit_square_sum(n)' inside the loop

Solution

1. Step 1: Analyze loop termination condition

   The loop only terminates when n == 1, but if n falls into an unhappy cycle, it never reaches 1.

2. Step 2: Identify missing cycle detection

   Without tracking seen numbers or using a known cycle set, the code loops infinitely for unhappy numbers.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Infinite loop occurs due to missing cycle detection [OK]

Hint: No cycle detection -> infinite loop on unhappy numbers [OK]

Common Mistakes:

• Assuming loop condition suffices
• Ignoring cycle detection necessity
• Misreading return placement

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