Reverse Integer

In this article, we will explore an efficient algorithm to reverse a 32 bit Integer. This involve edge cases where the reverse integer is out of bounds.

Table of contents:

1. Problem Statement
2. Algorithm to reverse a Number
3. Pseudocode
4. Code
5. Explanation
6. Time and Space Complexity

Let us get started with reversing a 32 bit Integer.

Problem Statement

Given a 32 bit number we have to reverse digit of that 32 bit integer and print reversed 32 bit number.

Example:

Input: 34924
Output: 42943

Input: -93432
Output: -23439

Algorithm to reverse a Number

Implementation of this problem is easy.
We will run a while loop till the number is greater than 0
inside while loop we will run following code

• reverseNo = reverseNo*10 + last digit of n

• reduce number by dividing with 10

• If number is negative then we can reverse number by making that positive and at last we can multiply that number with -1 to convert it into negative number

• But, we have edge cases here
  as in question it is mentioned that reverse number is also 32 bit
  Therefore we need to check that the reverse number can be stored in 32 bit int or not.

• If we can store reverse number 32 bit then, we will print that number
  else we will print "can't store reverse number in 32 bit"

• Also, of N is INT_MIN (-2147483648) then as number is negative so we can convert any negative number to positive by multiplying it with -1
  But here positive of N is 2147483648 which can be stored in int as max range of int is 2147483647

So, this is also an exceptional case.

Pseudocode

1. Take number N as input

2. Check if N is INT32_MIN

   • If Yes,
     • print "we can't store reverse of that number in 32 bit"
     • return

3. define boolean isNegative = false

4. check whether N is negative or not

5. If yes,

   • then isNegative = true

6. else,

   • isNegative = false

7. while(N is greater than 0)

   • check if reverse>INT32_MAX/10
   • if yes,
     • print "we can't store reverse of that number in 32 bit"
     • return
   • reverse = reverse*10 + N%10
   • N = N/10

8. print reverse

Code

Following is the implementation in C++:

#include<bits/stdc++.h>
using namespace std;

void solve() {
    int n, reverse=0; cin>>n;
    if(n==INT_MIN) {
        cout<<"reverse number can't be stored in 32 bits"<<endl;
        return;
    }
    bool isNegative = false;
    if(n<0) isNegative = true, n=-1*n;
    while(n>0) {
        if(reverse>INT32_MAX/10)  {
            cout<<"reverse number can't be stored in 32 bits"<<endl;
            return;
        }
        reverse = reverse*10 + n%10;
        n /= 10;
    }
    if(isNegative) cout<<-1*reverse<<endl;
    else cout<<reverse<<endl;
}

int main() {
    solve();
    return 0;
}

Input 1

-746384741

Output 1

-147483647

Input 2

2147483647

Output 2

reverse number can't be stored in 32 bits

Explanation

lets N = INT32_MAX = 2147483647

• first we will check if the number is INT_MIN or not as it is not then move forward
• as number is positive so isNegative = false
• then we will run while loop
• Inside while loop first we will check if number is greater than INT_MAX/10

Reason for doing this and writing this before performing reverse*10 + n%10 operation is
if number will be greater than INT_MAX/10 and if we multiply that number with 10
then it can be stored in int so its will get overflowed

Example:
if any int K = 2147483647 which is greater then INT_MAX/10=2147483647/10=214748364
if we multiply this by 10 : K = K * 10;
then if we print K then it will show K = -2147483626 in C++

Hence it get overflowed
so we need to first check if N > INT_MAX/10
if it is greater than INT_MAX/10 then we will just break the loop

if N < = INT_MAX/10 then we can run further iterations

for N => INT32_MAX => 2147483647
the following will be the 10 iterations

Initially,n= 2147483647 , reverse: 0

1. n= 214748364 , reverse: 7
2. n= 21474836 , reverse: 74
3. n= 2147483 , reverse: 746
4. n= 214748 , reverse: 7463
5. n= 21474 , reverse: 74638
6. n= 2147 , reverse: 746384
7. n= 214 , reverse: 7463847
8. n= 21 , reverse: 74638474
9. n= 2 , reverse: 746384741

and in 10th iteration when n= 2 , reverse: 746384741
we will check if (reverse > INT_MAX/10) => (746384741 > 2147483647/10)
so answer is true
Hence, we will break the loop and print “we can't reverse the number because we can't store the reverse of N in int”.

as we all know if we perform operation reverse*10 + n%10 without checking

then,
reverse = -1126087180
Hence if we perform operation without checking reverse will get overflowed

Time and Space Complexity

Time Complexity

• O(No of digits in number)
• As we are traversing loop till all the digits are visited

Space Complexity

• O(1)
• As one variable is created for storing reverse number