[7] Reverse Integer

© Jarvus Chen / www.jarvus.net

Description

Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

Hint: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Required knowledge

In 32-big signed integer, the range is -2^32 ~ 2^32 which is -2,147,483,648 ~ 2,147,483,647.

How to transfer int into char?

int x = -123;
char num[5];
sprintf(num,"%i",x);

Answers:

num[0] = '-'
num[1] = '1'
num[2] = '2'
num[3] = '3'
num[4] = ''

My solution

I separated my code into 4 steps. Step 1, for the easier operation, I extracted the sign of input value x which is positive or negative value. Moreover, if x equals -2147483648, it will overflow after x = -x.

Step 2, count how many digits are in the input value and use sprintf to allocate each digit. If count is 10 and the last digit is larger than 2, it will be a overflowed issue.

Step 3, result is sum of each digit*10 based. For example, num = [1, 2, 3, 4], sum = 4*10^(0) + 3*10^(1) + 2*10^(2) + 1*10^(3).

In the final step, Step 4, check result if it is always positive. Otherwise, it overflowed and then return 0.

int reverse(int x) {
    //step 1--------------------------------------------------
    if ( x == -2147483648 ){
        return 0;
    }
    int sign = 1;
    if ( x < 0 ){
        sign = -1;
        x = -x;
    }

    //step 2--------------------------------------------------
    int count = 1;
    char num[10];
    sprintf(num,"%d",x);
    while( x >= 10)
    {
        count++;
        x = x/10;
    }

    if ( count == 10 && (num[count-1]*1-48) > 2){
        return 0;
    }

    //step 3--------------------------------------------------
    int result = 0;
    for ( int i = 0 ; i < count; i++){
        result = result + (num[count-1-i]-48)*pow(10.0,count-i-1);
    }

    //step 4--------------------------------------------------
    if ( result < 0){
        return 0;
    }
    return result*sign;
}

Others solution

https://discuss.leetcode.com/topic/34506/8-ms-simple-c-solution-which-checks-overflow/3

There is a very clever way is using long long type. Its range is -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 so that you can process safely. In the equation, x%10 can get the last digit and x/=10 will update the last digit. Then, multiply 10 to go ahead to next digit. INT_MAX and INT_MIN is int range which are defined by the system.

int reverse(int x) {
   long long val = 0;
   do{
      val = val * 10 + x % 10;
      x /= 10;
   }while (x);
   return (val > INT_MAX || val < INT_MIN) ? 0 : val;
}