Palindrome Number

▶

Steps

setup

Check for negative or trailing zero

The algorithm first checks if the input number is negative or ends with zero (but is not zero itself). If so, it immediately returns false because such numbers cannot be palindromes.

💡 This step quickly eliminates impossible palindrome candidates, saving computation.

Line:

if x < 0 or (x % 10 == 0 and x != 0):
    return False

💡 Negative numbers and numbers ending with zero (except zero) cannot be palindromes.

setup

Initialize reversed_half to 0

The variable reversed_half is initialized to zero. This will hold the reversed digits of the second half of the number as we extract them.

💡 Starting reversed_half at zero is essential to build the reversed half incrementally.

Line:

reversed_half = 0

💡 We prepare a variable to store the reversed half of the number.

compare

Check loop condition x > reversed_half

The algorithm checks if the original number x is greater than reversed_half. Since 121 > 0, the loop will execute to extract digits.

💡 This condition controls how many digits we reverse - only half the number.

Line:

while x > reversed_half:

💡 We only reverse digits until reversed_half is at least half the number.

expand

Extract last digit and append to reversed_half

Extract the last digit of x (which is 1) and append it to reversed_half by multiplying reversed_half by 10 and adding the digit.

💡 This step builds reversed_half digit by digit from the end of x.

Line:

reversed_half = reversed_half * 10 + x % 10

💡 Appending digits in reverse order constructs the reversed half.

shrink

Remove last digit from x

Remove the last digit from x by integer division by 10, reducing x from 121 to 12.

💡 This step shrinks x as digits are moved to reversed_half.

Line:

x //= 10

💡 Shrinking x moves the algorithm closer to the midpoint.

compare

Check loop condition x > reversed_half again

Check if x (12) is still greater than reversed_half (1). Since 12 > 1, continue the loop.

💡 Loop continues until reversed_half is at least half the number.

Line:

while x > reversed_half:

💡 We still need to extract more digits.

expand

Extract last digit and append to reversed_half again

Extract last digit of x (2) and append it to reversed_half: reversed_half = 1 * 10 + 2 = 12.

💡 Appending next digit continues building reversed_half.

Line:

reversed_half = reversed_half * 10 + x % 10

💡 reversed_half now holds two digits reversed from the original number.

shrink

Remove last digit from x again

Remove last digit from x by integer division by 10, reducing x from 12 to 1.

💡 Shrinking x continues moving towards the midpoint.

Line:

x //= 10

💡 x now holds the remaining digits to compare with reversed_half.

compare

Check loop condition x > reversed_half again

Check if x (1) is greater than reversed_half (12). Since 1 > 12 is false, exit the loop.

💡 Loop ends when reversed_half is at least half the number.

Line:

while x > reversed_half:

💡 We have reversed half the digits needed for comparison.

compare

Compare x and reversed_half or reversed_half//10

Compare x (1) with reversed_half (12) and reversed_half // 10 (1). Since x equals reversed_half // 10, the number is a palindrome.

💡 For odd-length numbers, the middle digit is ignored by dividing reversed_half by 10.

Line:

return x == reversed_half or x == reversed_half // 10

💡 Ignoring the middle digit in odd-length numbers allows correct palindrome detection.

def is_palindrome(x: int) -> bool:
    # STEP 1: Check for negative or trailing zero
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    # STEP 2: Initialize reversed_half
    reversed_half = 0
    # STEP 3: Loop while x > reversed_half
    while x > reversed_half:
        # STEP 4: Append last digit of x to reversed_half
        reversed_half = reversed_half * 10 + x % 10
        # STEP 5: Remove last digit from x
        x //= 10
    # STEP 10: Compare halves
    return x == reversed_half or x == reversed_half // 10

📊

Palindrome Number - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how reversing only half the number optimizes the palindrome check without converting the number to a string.

compare

x

1

0

2

1

1

2

move_right

x

1

0

2

1

1

2

Result: 0

compare

x

1

0

2

1

1

2

Result: 0

expand

x

1

0

2

1

reversed_half

1

2

Result: 1

move_left

1

0

x

2

1

reversed_half

1

2

Result: 1

compare

1

0

x

2

1

reversed_half

1

2

Result: 1

expand

1

0

reversed_half

2

1

1

2

Result: 12

move_left

x

1

0

reversed_half

2

1

1

2

Result: 12

compare

x

1

0

reversed_half

2

1

1

2

Result: 12

compare

x

1

0

reversed_half

2

1

1

2

Result: true

Key Takeaways

✓ Reversing only half the number is enough to check palindrome property.

This optimization avoids overflow and unnecessary work compared to reversing the entire number.

✓ Ignoring the middle digit in odd-length numbers by dividing reversed_half by 10 is crucial.

It handles the center digit that doesn't affect palindrome symmetry.

✓ Early checks for negative numbers and trailing zeros quickly eliminate impossible palindromes.

This prevents wasted computation on numbers that cannot be palindromes.

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. You are given two rectangles on a 2D plane, each defined by their bottom-left and top-right coordinates. You need to determine if they overlap (i.e., share any area). Which approach guarantees an optimal and correct solution for this problem?

easy

A. Use a greedy algorithm to iteratively check if one rectangle can be shifted to overlap the other.

B. Check if the projections of the rectangles on both the x-axis and y-axis overlap using min and max coordinate comparisons.

C. Apply dynamic programming to store intermediate overlap states between sub-rectangles.

D. Use a brute force grid scan to check every point inside the bounding box of both rectangles.

Solution

1. Step 1: Understand the problem requires checking overlap on both axes

   Rectangles overlap if and only if their projections on the x-axis and y-axis overlap simultaneously.

2. Step 2: Recognize that comparing min and max coordinates on each axis is optimal

   Using min and max to find the intersection length on each axis is a constant-time, direct mathematical check.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking intervals on both axes ensures correct overlap detection [OK]

Hint: Check overlap on both x and y axes using min/max [OK]

Common Mistakes:

• Assuming overlap if only one axis overlaps
• Trying to solve with DP or greedy unnecessarily
• Using brute force scanning which is inefficient

3. Consider the following buggy code snippet for converting an Excel column title to a number. Which line contains the subtle bug that causes incorrect results for inputs like "A" or "Z"?

medium

A. Line 4: powers computation loop

B. Line 7: initialization of result

C. Line 9: calculation of value using zero-based indexing

D. Line 10: accumulation of result using powers

Solution

1. Step 1: Identify how letter values are computed

   The code uses ord(ch) - ord('A'), which makes 'A' = 0 instead of 1.

2. Step 2: Understand impact on result

   This causes all results to be off by one, e.g., "A" returns 0 instead of 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct letter values must be 1-based, not zero-based [OK]

Hint: Check if 'A' maps to 1, not 0 [OK]

Common Mistakes:

• Using zero-based indexing for letters
• Miscomputing powers array
• Incorrect accumulation order

4. What is the time and space complexity of the recursive digit extraction approach to reverse a 32-bit signed integer with d digits?

medium

A. Time: O(d), Space: O(d) -- linear digit processing and recursion stack depth equals digit count

B. Time: O(d^2), Space: O(1) -- due to repeated multiplication and no recursion stack

C. Time: O(d), Space: O(1) -- linear digit processing with constant auxiliary space

D. Time: O(1), Space: O(d) -- constant time due to fixed integer size but recursion stack grows

Solution

1. Step 1: Identify time complexity

   Each digit is processed once, so time is O(d) where d is number of digits.

2. Step 2: Identify space complexity

   Recursive calls stack up to d levels, so space is O(d) due to recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and recursion stack space matches digit count [OK]

Hint: Recursion stack adds O(d) space [OK]

Common Mistakes:

• Assuming constant space ignoring recursion stack
• Confusing digit count with input size n
• Thinking time is quadratic due to multiplication

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