Skip to main content

Leetcode 7: Reverse Integer


1. Problem Statement (Simple Explanation):


You are given a signed 32-bit integer x.

You need to:

  • Reverse its digits.

  • Return the reversed integer.

  • If the reversed integer is outside the 32-bit signed range:

                        [-231,231-1]=[-2147483648, 2147483647]

then return 0.

Additional constraint:

  • You cannot use 64-bit integers (so no long long, etc.).


2. Examples:


Example 1:

Input:           x = 123

                     Reversed digits: 321

Output:        321


Example 2:

Input:            x = -123

                      Reversed digits: -321 (the minus sign stays in front)

Output:         -321


Example 3:

Input:            x = 120

                      Reverse digits: 021 → 21

Output:         21


Constraints:           -231 ≤x≤ 231-1


3. Approach 1 – String Conversion (Conceptual, Not Recommended for Overflow Logic):


Intuition:


  • Convert x to a string.

  • Reverse the characters (excluding the sign).

  • Parse back to integer.

  • Check if it fits into 32-bit range.

But:

  • Requires careful handling of sign.

  • More importantly, per the constraint and typical interview expectations, you’re expected to do this using integer arithmetic, not by using long types or relying heavily on conversions.

  • Also you need to avoid 64-bit types for overflow handling.

We’ll focus on the integer arithmetic solution.


4. Approach 2 – Pop and Push Digits (Integer Arithmetic):


This is the standard and recommended solution.


Intuition:


We reverse the integer by:

  1. Repeatedly popping the last digit from x.

  2. Pushing that digit to the back of rev.

For example, starting with x = 123:

  • rev = 0

  • Pop 3 → digit = 3, x = 12 → rev = 0 * 10 + 3 = 3

  • Pop 2 → digit = 2, x = 1 → rev = 3 * 10 + 2 = 32

  • Pop 1 → digit = 1, x = 0 → rev = 32 * 10 + 1 = 321

We must ensure no overflow occurs when we compute:

rev=rev×10+digit

Because we can’t use 64-bit integers, we must detect overflow before it happens.


4.1 Popping the Last Digit:


To pop the last digit from x:

  • digit = x % 10

  • x = x / 10 (integer division)

This works for negative numbers too:

  • Example: x = -123
    digit = -123 % 10 = -3, x = -12.

So we don’t need to handle sign separately.


4.2 Overflow Check:


We need to ensure:

    INT_MIN <= rev * 10 + digit <= INT_MAX

where:

  • INT_MAX = 2147483647 (231-1)

  • INT_MIN = -2147483648 (-231)

We check before multiplying:

  • For positive side:

If rev > INT_MAX / 10, then rev * 10 will overflow.

If rev == INT_MAX / 10, then digit > 7 will overflow (because INT_MAX % 10 = 7).

  • For negative side:

If rev < INT_MIN / 10, then rev * 10 will underflow.

If rev == INT_MIN / 10, then digit < -8 will underflow (because INT_MIN % 10 = -8).

So if any of these conditions would be violated, we return 0.


Pseudo-code (Pop/Push with Overflow Check)


Note: In many languages you merge positive/negative checks compactly, but this version is explicit and interview-friendly.


Complexity:


Let k be the number of digits in x (at most 10 for 32-bit range):

  • Time: O(k)≈O(1)

  • Space: O(1)


5. Java code:


6. C code:


7. C++ code:


8. Python code:


Note: In Python, % and / behave differently for negatives than in C/Java.
Using int(x / 10) emulates truncation toward zero.


9. JavaScript code:




<<<PREV
NEXT>>>

Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more