Reverse Integer

📋

Problem

Imagine you are building a calculator app that needs to reverse the digits of an integer input by the user, but you must ensure the reversed number fits within 32-bit signed integer limits.

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

-2^31 <= x <= 2^31 - 1

Edge cases: x = 0 → output 0x = 1000000003 → output 0 (overflow after reversal)x = -2147483648 → output 0 (minimum 32-bit integer reversed overflows)

</>

IDE

def reverse(x: int) -> int:public int reverse(int x)int reverse(int x)function reverse(x)

def reverse(x: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int reverse(int x) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int reverse(int x) {
    // Write your solution here
    return 0;
}

function reverse(x) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 3210Returned reversed string or number without dropping leading zeros after reversal.✅ Convert reversed digits string to integer before returning to remove leading zeros.

Wrong: 1534236469Failed to detect overflow after reversal and returned original or incorrect reversed value.✅ Add explicit overflow check comparing reversed integer to 32-bit signed integer bounds before returning.

Wrong: -3000000001Overflow check missing for negative reversed integers.✅ Check reversed integer against lower bound -2^31 and return 0 if overflow.

Wrong: 0Incorrectly returning 0 for valid inputs like 10 reversed to 1.✅ Ensure reversal logic correctly handles trailing zeros and returns correct integer.

Wrong: Exception or crashNot handling zero or minimum integer input properly causing runtime errors.✅ Add explicit checks for zero input and handle minimum integer carefully to avoid overflow.

✓

Test Cases

Focus on handling zero, sign, and overflow edge cases carefully.

Test your code against tricky inputs with leading zeros and large values causing overflow.

Optimize your solution to run in linear time with constant space to avoid TLE.

t1_01basic

Input{"x":123}

Expected321

⏱ Performance - must finish in 2000ms

Reversing digits of 123 gives 321, which fits in 32-bit integer range.

💡 Think about reversing the digits by extracting them one by one.

💡 Check if the reversed number fits within the 32-bit signed integer range.

💡 Return 0 if overflow occurs; otherwise return the reversed integer.

Why it failed: Returned wrong reversed integer or failed to check overflow. Fix by verifying reversed value fits in [-2^31, 2^31-1] before returning.

✓ Correctly reversed digits and handled overflow.

t1_02basic

Input{"x":-123}

Expected-321

⏱ Performance - must finish in 2000ms

Reversing digits of -123 gives -321, which fits in 32-bit integer range.

💡 Remember to preserve the sign of the input integer.

💡 Extract digits from the absolute value and reapply the sign after reversal.

💡 Check overflow after reversing and before returning the result.

Why it failed: Sign handling incorrect or overflow check missing. Fix by applying sign after reversal and checking 32-bit bounds.

✓ Correctly reversed negative integer with proper overflow handling.

t2_01edge

Input{"x":0}

Expected0

⏱ Performance - must finish in 2000ms

Reversing 0 results in 0; edge case for zero input.

💡 Consider what happens when input is zero.

💡 Reversing zero should still return zero without errors.

💡 Ensure your code handles zero without unnecessary processing.

Why it failed: Failed to handle zero input correctly, possibly returning non-zero or error. Fix by explicitly returning 0 if input is 0.

✓ Correctly handled zero input.

t2_02edge

Input{"x":1000000003}

Expected0

⏱ Performance - must finish in 2000ms

Reversing 1000000003 results in 3000000001 which overflows 32-bit integer, so return 0.

💡 Check for overflow after reversal, especially for large inputs.

💡 Reversed number may exceed 2^31 - 1; return 0 in that case.

💡 Implement overflow detection before returning reversed integer.

Why it failed: Overflow not detected; returned incorrect large number. Fix by checking reversed integer within 32-bit signed range before returning.

✓ Correctly detected overflow and returned 0.

t2_03edge

Input{"x":-2147483648}

Expected0

⏱ Performance - must finish in 2000ms

Reversing minimum 32-bit integer overflows; must return 0.

💡 Minimum 32-bit integer reversed will overflow positive range.

💡 Check overflow for negative inputs as well.

💡 Return 0 if reversed integer is outside 32-bit signed integer bounds.

Why it failed: Failed to detect overflow for minimum integer input. Fix by applying overflow check symmetrically for negative values.

✓ Correctly handled minimum 32-bit integer overflow.

t3_01corner

Input{"x":10}

Expected1

⏱ Performance - must finish in 2000ms

Reversing 10 results in 01 which is 1 after dropping leading zeros.

💡 Leading zeros in reversed number should be dropped.

💡 Convert reversed digits back to integer to remove leading zeros.

💡 Do not return reversed string; convert to int before returning.

Why it failed: Returned reversed string or number with leading zeros. Fix by converting reversed digits to integer to drop leading zeros.

✓ Correctly dropped leading zeros after reversal.

t3_02corner

Input{"x":1534236469}

Expected0

⏱ Performance - must finish in 2000ms

Reversing 1534236469 causes overflow; must return 0.

💡 Large inputs may cause overflow after reversal.

💡 Check overflow before returning reversed integer.

💡 Return 0 if reversed integer exceeds 32-bit signed integer range.

Why it failed: Overflow not detected for large input; returned incorrect value. Fix by adding overflow check before return.

✓ Correctly detected overflow and returned 0.

t3_03corner

Input{"x":-1000000003}

Expected0

⏱ Performance - must finish in 2000ms

Reversing -1000000003 results in -3000000001 which overflows; return 0.

💡 Negative large inputs can overflow after reversal.

💡 Apply overflow check for negative reversed integers.

💡 Return 0 if reversed integer is outside 32-bit signed integer range.

Why it failed: Failed to detect overflow for negative large input. Fix by checking reversed integer bounds for negative values.

✓ Correctly handled overflow for negative large input.

t4_01performance

Input{"_description":"n=100 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 digits (max length integer) must complete in O(d) time within 2 seconds.

💡 Algorithm should run in linear time relative to number of digits.

💡 Avoid exponential or recursive solutions that cause TLE.

💡 Use iterative digit extraction and overflow checks for efficiency.

Why it failed: Solution exceeds time limit due to inefficient digit processing or recursion. Fix by using iterative O(d) approach with constant space.

✓ Solution runs efficiently in linear time with respect to digit count.

Practice

1. You need to find the smallest angle between the hour and minute hands of a clock given any time. Which approach guarantees an optimal and correct solution for all valid inputs?

easy

A. Use a greedy approach that moves the hour hand in fixed 30-degree increments ignoring minutes.

B. Calculate the exact angles of hour and minute hands considering minute progress, then find the minimal difference.

C. Apply dynamic programming to store intermediate angles for subproblems of time intervals.

D. Use a brute force simulation checking every possible angle from 0 to 360 degrees.

Solution

1. Step 1: Understand the problem requirements

   The problem requires calculating the minimal angle between two clock hands at any given time, which depends on both hour and minute positions.

2. Step 2: Evaluate approaches

   Greedy ignoring minute progress fails for times like 3:30. DP is unnecessary as the problem is direct calculation, and brute force is inefficient. Calculating exact angles considering minute progress ensures correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minute progress affects hour hand angle -> correct calculation needed [OK]

Hint: Hour hand moves with minutes; ignore minute progress -> wrong [OK]

Common Mistakes:

• Ignoring minute contribution to hour hand angle
• Using greedy increments without minute adjustment

2. Consider the following code snippet intended to find the minimum area rectangle from a list of points. Which line contains a subtle bug that can cause incorrect results?

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 == x2 or y1 == y2:
                continue
            if (x1, y2) in point_set and (x2, y1) in point_set:
                area = abs(x1 - x2) * abs(y1 - y2)
                if area < min_area:
                    min_area = area
    return min_area

medium

A. Line checking if x1 == x2 or y1 == y2 to skip invalid diagonals

B. Line calculating area as abs(x1 - x2) * abs(y1 - y2)

C. Line returning min_area without checking if it is still infinity

D. Line creating the point_set from points

Solution

1. Step 1: Identify the return statement

   The code returns min_area directly, which may be float('inf') if no rectangle is found.

2. Step 2: Understand the consequence

   Returning float('inf') is incorrect; the function should return 0 if no rectangle exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Return without check -> wrong output if no rectangle [OK]

Hint: Always check if min_area updated before returning [OK]

Common Mistakes:

• Forgetting to return 0 if no rectangle found
• Skipping diagonal check conditions

3. What is the time complexity of the optimal palindrome number check algorithm that reverses half of the digits, and why?

medium

A. O(log n), where n is the integer value, because the number of digits is proportional to log base 10 of n.

B. O(n), where n is the number of digits, because it processes each digit once.

C. O(n^2), because reversing digits involves nested operations on each digit.

D. O(1), because it only reverses half the digits regardless of input size.

Solution

1. Step 1: Identify input size parameter

   Input is an integer n; number of digits d = floor(log10(n)) + 1.

2. Step 2: Analyze loop iterations

   The loop runs until reversed_half >= x, roughly half the digits processed -> O(d).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time depends on digit count, which is linear in number of digits [OK]

Hint: Time depends on digit count, not numeric value directly [OK]

Common Mistakes:

• Confusing n as digit count vs integer value
• Assuming O(1) due to half reversal
• Mistaking nested loops cause O(n^2)

4. What is the time complexity of the optimal single-pass Roman to Integer conversion algorithm, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character is compared with all others

B. O(n) because each character is processed once with constant-time operations

C. O(n log n) due to sorting or searching steps

D. O(n) but with O(n) auxiliary space for storing intermediate results

Solution

1. Step 1: Identify the loops and operations

   The algorithm iterates over the input string once, performing constant-time comparisons and arithmetic per character.

2. Step 2: Address common misconceptions

   Some candidates mistakenly think the complexity is O(n^2) by assuming nested loops or repeated lookups, but no nested iteration occurs; no sorting or extra data structures are used.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Actual complexity is O(n), but candidates often incorrectly assume O(n^2) [Trap]

Hint: Single loop with constant work per char -> O(n) [OK]

Common Mistakes:

• Assuming nested loops
• Confusing auxiliary space with time
• Thinking sorting is involved

5. Suppose the problem is modified so that negative integers can also be palindromes if their absolute values are palindromes (e.g., -121 is considered palindrome). Which modification to the optimal algorithm correctly handles this variant?

hard

A. Take the absolute value of the input at the start and proceed with the half reversal algorithm.

B. Remove the negative number check and reverse the entire number instead of half.

C. Convert the number to string including the sign and check palindrome with two pointers.

D. Ignore the sign and compare digits from both ends using modulo and division without reversal.

Solution

1. Step 1: Understand new requirement

   Negative numbers are palindrome if their absolute values are palindromes.

2. Step 2: Modify algorithm accordingly

   Taking absolute value removes sign issue; then half reversal works unchanged.

3. Step 3: Evaluate other options

   Removing negative check without abs causes errors; full reversal risks overflow; string conversion uses extra space; digit comparison without reversal is complex.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Absolute value preserves palindrome property and fits optimal approach [OK]

Hint: Use absolute value to handle sign, keep optimal logic [OK]

Common Mistakes:

• Removing negative check without abs
• Switching to full reversal causing overflow
• Using string conversion losing O(1) space