Reverse Integer Solution for Accenture

Company: Accenture · Difficulty: Medium · Topics: Math

Problem Statement

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 [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Key Understanding:

Reverse the digits of a 32-bit integer
Handle negative numbers (preserve the sign)
Check for overflow/underflow at each step
Return 0 if result exceeds 32-bit range
Cannot use 64-bit integers for intermediate calculations

Examples

Example 1:

Input: x = 123

Output: 321

Explanation:

Step 1: Extract last digit: 123 % 10 = 3, result = 3, x = 12
Step 2: Extract last digit: 12 % 10 = 2, result = 3×10 + 2 = 32, x = 1
Step 3: Extract last digit: 1 % 10 = 1, result = 32×10 + 1 = 321, x = 0
Result: 321

Example 2:

Input: x = -123

Output: -321

Explanation:

Step 1: Extract last digit: 123 % 10 = 3, result = 3, x = 12
Step 2: Extract last digit: 12 % 10 = 2, result = 3×10 + 2 = 32, x = 1
Step 3: Extract last digit: 1 % 10 = 1, result = 32×10 + 1 = 321, x = 0
Apply sign: -321
Result: -321

Example 3:

Input: x = 120

Output: 21

Explanation:

Step 1: Extract last digit: 120 % 10 = 0, result = 0, x = 12
Step 2: Extract last digit: 12 % 10 = 2, result = 0×10 + 2 = 2, x = 1
Step 3: Extract last digit: 1 % 10 = 1, result = 2×10 + 1 = 21, x = 0
Result: 21 (leading zeros are ignored)

Example 4:

Input: x = 1534236469

Output: 0

Explanation:

Overflow occurs: Reverse would be 9646324351
32-bit range: [-2,147,483,648 to 2,147,483,647]
9646324351 > 2,147,483,647 (overflow)
Result: 0

Example 5:

Input: x = 0

Output: 0

Explanation:

Single digit number, no reversal needed
Result: 0

Intuition

The key insight is to extract digits one by one and build the reversed number. We need to handle overflow carefully by checking before multiplying by 10.

Why This Approach Works:

We extract the last digit using modulo operation (x % 10)
We build the result by multiplying by 10 and adding the new digit
We continue until x becomes 0
We handle negative numbers by working with absolute value and applying sign at the end

Overflow Detection Strategy:

Before multiplying by 10, check if result > INT_MAX/10
If equal to INT_MAX/10, check if next digit > 7 (for positive) or > 8 (for negative)
This prevents overflow without using 64-bit integers

Approach

Approach 1: Mathematical with Overflow Detection (Optimal)

Algorithm:

1. Handle edge case: if x = 0, return 0

2. Extract last digit using modulo: digit = x % 10

3. Check for overflow before multiplying result by 10

4. Build reversed number: result = result * 10 + digit

5. Remove last digit: x = x / 10

6. Repeat until x = 0

7. Apply original sign

Overflow Check:

For positive numbers: result > INT_MAX/10 OR (result == INT_MAX/10 AND digit > 7)
For negative numbers: result < INT_MIN/10 OR (result == INT_MIN/10 AND digit < -8)

Approach 2: String Conversion

Algorithm:

1. Convert integer to string

2. Reverse the string (excluding sign)

3. Convert back to integer

4. Handle overflow using long long

5. Apply sign

Approach 3: Power-based Approach

Algorithm:

1. Count number of digits

2. Use powers of 10 to reverse

3. Check for overflow at each step

4. Apply sign

Dry Run

Let's trace through Example 1: x = 123

Step-by-Step Process:

1. Initial: x = 123, result = 0

2. Step 1: digit = 123 % 10 = 3

Check overflow: 0 ≤ INT_MAX/10 (214748364) ✓
result = 0 × 10 + 3 = 3
x = 123 / 10 = 12

3. Step 2: digit = 12 % 10 = 2

Check overflow: 3 ≤ INT_MAX/10 ✓
result = 3 × 10 + 2 = 32
x = 12 / 10 = 1

4. Step 3: digit = 1 % 10 = 1

Check overflow: 32 ≤ INT_MAX/10 ✓
result = 32 × 10 + 1 = 321
x = 1 / 10 = 0

5. Result: 321

Overflow Example: x = 1534236469

1. Step 1: digit = 9, result = 9

2. Step 2: digit = 6, result = 96

3. ... continues until overflow occurs

4. Overflow detected: return 0

Key Insights

1. Modulo Operation: x % 10 gives the last digit

2. Integer Division: x / 10 removes the last digit

3. Overflow Prevention: Check before multiplication, not after

4. Sign Handling: Work with absolute value, apply sign at end

5. Leading Zeros: Automatically handled by integer arithmetic

6. Edge Cases: 0, single digits, negative numbers

Edge Cases

1. x = 0: Return 0

2. Single digit: Return the same number

3. Negative numbers: Handle sign separately

4. Overflow cases: Return 0

5. Large numbers: Careful overflow detection

6. Numbers ending in 0: Leading zeros are ignored

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Mathematical with Overflow Detection (Optimal)

Time Complexity: O(log n) - Number of digits

Space Complexity: O(1) - Constant space

Solution 2: String Conversion

Time Complexity: O(log n) - String operations

Space Complexity: O(log n) - String storage

Solution 3: Power-based Approach

Time Complexity: O(log n) - Multiple passes

Space Complexity: O(1) - Constant space