Reverse Integer

🎯

Reverse Integer

mediumMATHAmazonGoogleBloomberg

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.

💡 This problem is about manipulating digits of an integer and handling edge cases like overflow. Beginners often struggle with extracting digits correctly and ensuring the reversed number doesn't exceed integer bounds.

📋

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

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

💡

Example

Input"x = 123"

Output321

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

Input"x = -123"

Output-321

Negative sign is preserved, digits reversed.

Input"x = 120"

Output21

Trailing zeros are dropped after reversal.

Input"x = 1534236469"

Output0

Reversed integer overflows 32-bit signed integer range, so return 0.

• x = 0 → output 0
• x = 1000000003 → output 0 (overflow after reversal)
• x = -2147483648 → output 0 (minimum 32-bit integer reversed overflows)
• x = 10 → output 1 (leading zeros dropped after reversal)

⚠️

Common Mistakes

Ignoring sign and reversing absolute value only

Output is always positive, incorrect for negative inputs

✅ Store sign before reversal and reapply after reversal

Not checking overflow before multiplying by 10

Integer overflow causes wrong output or runtime error

✅ Check if rev > INT_MAX/10 or equal and next digit > 7 before multiplying

Using string conversion but not handling leading zeros after reversal

Output may have leading zeros or incorrect integer value

✅ Convert reversed string to int to automatically remove leading zeros

Using recursion without base case or overflow check

Stack overflow or incorrect results

✅ Implement base case and overflow checks in recursive calls

Using 64-bit integer type but returning 32-bit int without overflow check

Overflow not detected, incorrect output

✅ Explicitly check reversed number against 32-bit limits before returning

🧠

Brute Force (String Conversion)

💡 This approach uses string manipulation to reverse digits, which is intuitive but not optimal for integer overflow handling. It helps beginners understand digit reversal conceptually.

Intuition

Convert the integer to a string, reverse the string, then convert back to integer while preserving the sign.

Algorithm

1. Convert integer to string.
2. If negative, remove the sign and remember it.
3. Reverse the string of digits.
4. Convert reversed string back to integer and reapply sign.
5. Check for 32-bit overflow; if overflow, return 0.

💡 The main challenge is remembering to handle the sign and overflow after reversal.

</>

Code

def reverse(x: int) -> int:
    sign = -1 if x < 0 else 1
    s = str(abs(x))
    rev_s = s[::-1]
    rev_int = sign * int(rev_s)
    if rev_int < -2**31 or rev_int > 2**31 - 1:
        return 0
    return rev_int

# Driver code
if __name__ == '__main__':
    test_cases = [123, -123, 120, 1534236469]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {reverse(tc)}")

Line Notes

sign = -1 if x < 0 else 1Determine the sign of the input to reapply later.

s = str(abs(x))Convert absolute value of integer to string to manipulate digits.

rev_s = s[::-1]Reverse the string using slicing.

rev_int = sign * int(rev_s)Convert reversed string back to integer and apply sign.

if rev_int < -2**31 or rev_int > 2**31 - 1:Check for 32-bit signed integer overflow.

return 0Return 0 if overflow detected.

return rev_intReturn the reversed integer if valid.

public class Solution {
    public int reverse(int x) {
        int sign = x < 0 ? -1 : 1;
        String s = Integer.toString(Math.abs(x));
        String rev_s = new StringBuilder(s).reverse().toString();
        try {
            long rev_long = Long.parseLong(rev_s);
            if (rev_long > Integer.MAX_VALUE) {
                return 0;
            }
            int rev_int = sign * (int) rev_long;
            if (rev_int < Integer.MIN_VALUE) {
                return 0;
            }
            return rev_int;
        } catch (NumberFormatException e) {
            return 0;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] testCases = {123, -123, 120, 1534236469};
        for (int tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + sol.reverse(tc));
        }
    }
}

Line Notes

int sign = x < 0 ? -1 : 1;Determine sign of input integer.

String s = Integer.toString(Math.abs(x));Convert absolute value to string for reversal.

String rev_s = new StringBuilder(s).reverse().toString();Reverse the string using StringBuilder.

long rev_long = Long.parseLong(rev_s);Parse reversed string as long to detect overflow.

if (rev_long > Integer.MAX_VALUE)Check if reversed number exceeds 32-bit max integer.

int rev_int = sign * (int) rev_long;Apply sign after confirming no overflow.

if (rev_int < Integer.MIN_VALUE)Check if reversed number is below 32-bit min integer.

return 0;Return 0 if overflow occurs.

return rev_int;Return reversed integer if no overflow.

#include <iostream>
#include <string>
#include <climits>
using namespace std;

int reverse(int x) {
    int sign = x < 0 ? -1 : 1;
    string s = to_string(abs(x));
    reverse(s.begin(), s.end());
    long long rev_int = sign * stoll(s);
    if (rev_int < INT_MIN || rev_int > INT_MAX) return 0;
    return (int)rev_int;
}

int main() {
    int testCases[] = {123, -123, 120, 1534236469};
    for (int tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << reverse(tc) << endl;
    }
    return 0;
}

Line Notes

int sign = x < 0 ? -1 : 1;Determine sign of input integer.

string s = to_string(abs(x));Convert absolute value to string for reversal.

reverse(s.begin(), s.end());Reverse the string in place using STL reverse.

long long rev_int = sign * stoll(s);Convert reversed string to long long to detect overflow.

if (rev_int < INT_MIN || rev_int > INT_MAX) return 0;Check for 32-bit integer overflow.

return (int)rev_int;Return reversed integer if valid.

cout << ...Print test case results.

var reverse = function(x) {
    const sign = x < 0 ? -1 : 1;
    const s = Math.abs(x).toString();
    const rev_s = s.split('').reverse().join('');
    const rev_int = sign * Number(rev_s);
    if (rev_int < -(2**31) || rev_int > 2**31 - 1) return 0;
    return rev_int;
};

// Test cases
[123, -123, 120, 1534236469].forEach(tc => {
    console.log(`Input: ${tc} -> Output: ${reverse(tc)}`);
});

Line Notes

const sign = x < 0 ? -1 : 1;Determine sign of input integer.

const s = Math.abs(x).toString();Convert absolute value to string for reversal.

const rev_s = s.split('').reverse().join('');Reverse string by splitting, reversing array, and joining.

const rev_int = sign * Number(rev_s);Convert reversed string back to number and apply sign.

if (rev_int < -(2**31) || rev_int > 2**31 - 1) return 0;Check for 32-bit integer overflow.

return rev_int;Return reversed integer if valid.

console.log(...)Print test case results.

⏱

Complexity

TimeO(d) where d is number of digits in x

SpaceO(d) for string storage

Converting to string and reversing takes linear time and space proportional to number of digits.

💡 For a 10-digit number, this means about 10 operations for reversal, which is efficient but not optimal for integer-only manipulation.

Interview Verdict: Accepted but not optimal

This approach works but relies on string conversion and exception handling, which might not be allowed or efficient in some interviews.

🧠

Digit Extraction and Rebuild (Iterative)

💡 This approach uses pure integer math to extract and rebuild the reversed number digit by digit, avoiding string conversions and handling overflow explicitly.

Intuition

Extract digits from the end using modulo and build the reversed number by multiplying the accumulator by 10 and adding the extracted digit.

Algorithm

1. Initialize reversed number as 0.
2. While input is not zero, extract last digit using modulo 10.
3. Check if appending this digit causes overflow.
4. Multiply reversed number by 10 and add extracted digit.
5. Divide input by 10 to remove last digit.
6. Return reversed number after loop ends.

💡 The key difficulty is correctly checking overflow before it happens to avoid incorrect results.

</>

Code

def reverse(x: int) -> int:
    rev = 0
    sign = -1 if x < 0 else 1
    x = abs(x)
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    while x != 0:
        pop = x % 10
        x //= 10
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
            return 0
        rev = rev * 10 + pop
    return sign * rev

# Driver code
if __name__ == '__main__':
    test_cases = [123, -123, 120, 1534236469]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {reverse(tc)}")

Line Notes

rev = 0Initialize accumulator for reversed number.

sign = -1 if x < 0 else 1Store sign to reapply later.

x = abs(x)Work with absolute value for digit extraction.

pop = x % 10Extract last digit of current number.

x //= 10Remove last digit from number.

if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7)Check if next step causes overflow.

rev = rev * 10 + popAppend extracted digit to reversed number.

return sign * revReturn reversed number with original sign.

public class Solution {
    public int reverse(int x) {
        int rev = 0;
        int sign = x < 0 ? -1 : 1;
        x = Math.abs(x);
        int INT_MAX = Integer.MAX_VALUE;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) {
                return 0;
            }
            rev = rev * 10 + pop;
        }
        return sign * rev;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] testCases = {123, -123, 120, 1534236469};
        for (int tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + sol.reverse(tc));
        }
    }
}

Line Notes

int rev = 0;Initialize reversed number accumulator.

int sign = x < 0 ? -1 : 1;Store sign for later.

x = Math.abs(x);Work with absolute value for digit extraction.

int pop = x % 10;Extract last digit.

x /= 10;Remove last digit.

if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7))Check for overflow before appending digit.

rev = rev * 10 + pop;Append digit to reversed number.

return sign * rev;Return reversed number with sign.

#include <iostream>
#include <climits>
using namespace std;

int reverse(int x) {
    int rev = 0;
    int sign = x < 0 ? -1 : 1;
    x = abs(x);
    while (x != 0) {
        int pop = x % 10;
        x /= 10;
        if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
        rev = rev * 10 + pop;
    }
    return sign * rev;
}

int main() {
    int testCases[] = {123, -123, 120, 1534236469};
    for (int tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << reverse(tc) << endl;
    }
    return 0;
}

Line Notes

int rev = 0;Initialize reversed number accumulator.

int sign = x < 0 ? -1 : 1;Store sign for later.

x = abs(x);Work with absolute value for digit extraction.

int pop = x % 10;Extract last digit.

x /= 10;Remove last digit.

if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;Check for overflow before appending digit.

rev = rev * 10 + pop;Append digit to reversed number.

return sign * rev;Return reversed number with sign.

var reverse = function(x) {
    let rev = 0;
    const sign = x < 0 ? -1 : 1;
    x = Math.abs(x);
    const INT_MAX = 2**31 - 1;
    while (x !== 0) {
        let pop = x % 10;
        x = Math.floor(x / 10);
        if (rev > Math.floor(INT_MAX / 10) || (rev === Math.floor(INT_MAX / 10) && pop > 7)) {
            return 0;
        }
        rev = rev * 10 + pop;
    }
    return sign * rev;
};

// Test cases
[123, -123, 120, 1534236469].forEach(tc => {
    console.log(`Input: ${tc} -> Output: ${reverse(tc)}`);
});

Line Notes

let rev = 0;Initialize reversed number accumulator.

const sign = x < 0 ? -1 : 1;Store sign for later.

x = Math.abs(x);Work with absolute value for digit extraction.

let pop = x % 10;Extract last digit.

x = Math.floor(x / 10);Remove last digit.

if (rev > Math.floor(INT_MAX / 10) || (rev === Math.floor(INT_MAX / 10) && pop > 7))Check for overflow before appending digit.

rev = rev * 10 + pop;Append digit to reversed number.

return sign * rev;Return reversed number with sign.

⏱

Complexity

TimeO(d) where d is number of digits

SpaceO(1) constant space

Each digit is processed once, and only a few variables are used.

💡 For a 10-digit number, about 10 iterations happen, which is efficient and uses minimal memory.

Interview Verdict: Accepted and optimal

This approach is preferred in interviews because it uses integer operations only and handles overflow explicitly.

🧠

Recursive Digit Extraction

💡 This approach uses recursion to reverse digits by peeling off digits from the end and building the reversed number during the recursion unwind. It is less common but helps understand recursion with integer math.

Intuition

Recursively extract the last digit and build the reversed number by passing an accumulator through recursive calls.

Algorithm

1. Define a helper recursive function with current number and accumulator.
2. Base case: if number is 0, return accumulator.
3. Extract last digit using modulo 10.
4. Check if appending digit causes overflow.
5. Recurse with number divided by 10 and updated accumulator.
6. Return final reversed number with sign.

💡 The challenge is managing accumulator and overflow checks correctly in recursion.

</>

Code

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

    def helper(num, rev):
        if num == 0:
            return rev
        pop = num % 10
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
            return 0
        return helper(num // 10, rev * 10 + pop)

    rev = helper(x, 0)
    return sign * rev if rev != 0 else 0

# Driver code
if __name__ == '__main__':
    test_cases = [123, -123, 120, 1534236469]
    for tc in test_cases:
        print(f"Input: {tc} -> Output: {reverse(tc)}")

Line Notes

sign = -1 if x < 0 else 1Store sign for later reapplication.

x = abs(x)Work with absolute value for digit extraction.

def helper(num, rev):Recursive helper function with current number and reversed accumulator.

if num == 0:Base case: no more digits to process.

pop = num % 10Extract last digit.

if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7)Check for overflow before appending digit.

return helper(num // 10, rev * 10 + pop)Recurse with next digit and updated reversed number.

return sign * rev if rev != 0 else 0Return reversed number with sign or 0 if overflow.

public class Solution {
    private static final int INT_MAX = Integer.MAX_VALUE;
    private static final int INT_MIN = Integer.MIN_VALUE;

    public int reverse(int x) {
        int sign = x < 0 ? -1 : 1;
        x = Math.abs(x);
        int rev = helper(x, 0);
        return rev == 0 ? 0 : sign * rev;
    }

    private int helper(int num, int rev) {
        if (num == 0) return rev;
        int pop = num % 10;
        if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
        return helper(num / 10, rev * 10 + pop);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] testCases = {123, -123, 120, 1534236469};
        for (int tc : testCases) {
            System.out.println("Input: " + tc + " -> Output: " + sol.reverse(tc));
        }
    }
}

Line Notes

int sign = x < 0 ? -1 : 1;Store sign for later.

x = Math.abs(x);Work with absolute value.

int rev = helper(x, 0);Call recursive helper with initial accumulator 0.

if (num == 0) return rev;Base case for recursion.

int pop = num % 10;Extract last digit.

if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;Check overflow before appending.

return helper(num / 10, rev * 10 + pop);Recursive call with updated values.

return rev == 0 ? 0 : sign * rev;Return reversed number with sign or 0 if overflow.

#include <iostream>
#include <climits>
using namespace std;

int helper(int num, int rev) {
    if (num == 0) return rev;
    int pop = num % 10;
    if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
    return helper(num / 10, rev * 10 + pop);
}

int reverse(int x) {
    int sign = x < 0 ? -1 : 1;
    x = abs(x);
    int rev = helper(x, 0);
    return rev == 0 ? 0 : sign * rev;
}

int main() {
    int testCases[] = {123, -123, 120, 1534236469};
    for (int tc : testCases) {
        cout << "Input: " << tc << " -> Output: " << reverse(tc) << endl;
    }
    return 0;
}

Line Notes

if (num == 0) return rev;Base case for recursion.

int pop = num % 10;Extract last digit.

if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;Check overflow before appending.

return helper(num / 10, rev * 10 + pop);Recursive call with updated values.

int sign = x < 0 ? -1 : 1;Store sign for later.

x = abs(x);Work with absolute value.

int rev = helper(x, 0);Call recursive helper.

return rev == 0 ? 0 : sign * rev;Return reversed number with sign or 0 if overflow.

var reverse = function(x) {
    const INT_MAX = 2**31 - 1;
    const sign = x < 0 ? -1 : 1;
    x = Math.abs(x);

    function helper(num, rev) {
        if (num === 0) return rev;
        let pop = num % 10;
        if (rev > Math.floor(INT_MAX / 10) || (rev === Math.floor(INT_MAX / 10) && pop > 7)) return 0;
        return helper(Math.floor(num / 10), rev * 10 + pop);
    }

    const rev = helper(x, 0);
    return rev === 0 ? 0 : sign * rev;
};

// Test cases
[123, -123, 120, 1534236469].forEach(tc => {
    console.log(`Input: ${tc} -> Output: ${reverse(tc)}`);
});

Line Notes

const sign = x < 0 ? -1 : 1;Store sign for later.

x = Math.abs(x);Work with absolute value.

function helper(num, rev)Recursive helper function with accumulator.

if (num === 0) return rev;Base case for recursion.

let pop = num % 10;Extract last digit.

if (rev > Math.floor(INT_MAX / 10) || (rev === Math.floor(INT_MAX / 10) && pop > 7)) return 0;Check overflow before appending.

return helper(Math.floor(num / 10), rev * 10 + pop);Recursive call with updated values.

return rev === 0 ? 0 : sign * rev;Return reversed number with sign or 0 if overflow.

⏱

Complexity

TimeO(d) where d is number of digits

SpaceO(d) due to recursion stack

Each digit is processed once, but recursion adds stack overhead proportional to digits.

💡 For a 10-digit number, recursion depth is 10, which is manageable but less efficient than iteration.

Interview Verdict: Accepted but less preferred

Recursion shows understanding but risks stack overflow and is less efficient than iterative approach.

📊

All Approaches - One-Glance Tradeoffs

💡 The iterative digit extraction approach is the best choice for interviews due to efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (String Conversion)	O(d)	O(d)	No	N/A	Mention only - easy to explain but less optimal
2. Iterative Digit Extraction	O(d)	O(1)	No	N/A	Code this - optimal and interview favorite
3. Recursive Digit Extraction	O(d)	O(d)	Yes (deep recursion)	N/A	Mention to show recursion knowledge, but avoid coding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input range and overflow requirements.Step 2: Present brute force string conversion approach for clarity.Step 3: Discuss iterative digit extraction with overflow checks as optimal.Step 4: Optionally mention recursive approach to show depth of understanding.Step 5: Code the iterative approach and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to manipulate digits, handle sign and overflow, and write clean, efficient code.

Common Follow-ups

• What if the integer size changes? → Adjust overflow checks accordingly.
• Can you do it without converting to string? → Use digit extraction approach.

💡 These follow-ups test your understanding of integer limits and ability to optimize solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves reversing digits of an integer; 2) Overflow or boundary conditions matter; 3) Sign preservation is required; 4) Digit extraction or manipulation is needed.

Signature Phrases

reverse digits32-bit signed integeroverflow check

NOT This Pattern When

Problems that reverse strings or arrays without integer overflow concerns.

Similar Problems

Palindrome Number - also involves digit manipulationInteger to Roman - digit extraction and encodingString to Integer (atoi) - parsing and overflow handling

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

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

4. Suppose you want to extend the happy number check to negative integers by applying the same digit square sum process on their absolute values. Which modification to the algorithm is necessary to correctly handle negative inputs?

hard

A. Add a check to convert negative input to positive before processing digits.

B. Modify digit extraction to handle negative digits directly without conversion.

C. Use recursion instead of iteration to handle negative inputs.

D. No modification needed; the existing algorithm works for negative numbers.

Solution

1. Step 1: Understand digit extraction for negatives

   Digit extraction using modulo and division assumes non-negative numbers; negative digits do not exist.

2. Step 2: Convert negative input to positive

   Taking absolute value ensures digit extraction works correctly and the sum of squares is computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value conversion fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Trying to extract digits from negative directly
• Assuming recursion helps
• Ignoring sign issues

5. Suppose the problem is modified so that points can have negative coordinates and the input size is very large. Which modification to the optimal approach is necessary to maintain efficiency and correctness?

hard

A. Use a hash set as before, since it supports negative coordinates and lookups remain O(1).

B. Replace the hash set with a balanced binary search tree to handle negative coordinates efficiently.

C. Sort points by coordinates and use two pointers to find rectangles, avoiding hash sets.

D. Switch to brute force checking all quadruples since negative coordinates break the hash set approach.

Solution

1. Step 1: Consider data structure requirements

   Hash sets in Python support negative integers as keys with O(1) average lookup time.

2. Step 2: Evaluate alternatives

   Replacing with balanced trees adds unnecessary overhead; sorting and two pointers do not guarantee rectangle detection efficiently; brute force is too slow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set handles negative coords efficiently -> no change needed [OK]

Hint: Hash sets handle negative keys naturally [OK]

Common Mistakes:

• Thinking hash sets can't handle negative keys
• Switching to slower data structures unnecessarily