Reverse integer in c gives overflow

Question

I am solving reverse integer problem in leetcode in c language.But it gives runtime error on line sum=sum+rem*10;.

runtime error: signed integer overflow: 964632435 * 10 cannot be represented in type 'int'

Here is the code.

#define INT_MAX 2147483647
#define INT_MIN -2147483648

int reverse(int x){
    int sum=0,rem=0;
    int p;
    if(x > INT_MAX || x < INT_MIN){return 0;}
    if(x==0){return 0;}
    if(x<0){p=x;x=abs(x);}
    while(x%10==0){x=x/10;}

    while(x>0){
        rem=x%10;

        if(sum > INT_MAX || sum*(-1) < INT_MIN){return 0;}        
        sum=sum*10+rem;

        x/=10;
    }
    if(p<0){sum=sum*(-1);return sum;}
    else{return sum;}
}

if(x > INT_MAX || x < INT_MIN){return 0;} How do you expect an integer x to be greater than INT_MAX or less than INT_MIN? — 4386427
– 4386427, Commented Apr 24, 2020 at 14:41
Remember - not all integer values can be reversed an still fit into an integer — 4386427
– 4386427, Commented Apr 24, 2020 at 14:44

4386427 · Accepted Answer · 2020-04-24 17:28:39Z

One way - which isn't performance optimal but simple - is to convert the integer to a string and then revert the string and then convert back to integer.

The below solution is for positive integers - I'll leave it to OP to extend it to handle negative integers.

Could look like:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int reverse(const int n)
{
    if (n < 0)
    {
        printf("Handling of negative integers must be added\n");
        exit(1);
    }

    char tmp1[100];
    char tmp2[100] = { 0 };
    sprintf(tmp1, "%d", n);
    printf("Input : %s\n", tmp1);
    size_t sz = strlen(tmp1);
    for (size_t i = 0; i < sz; ++i)
    {
        tmp2[i] = tmp1[sz-i-1];
    }

    int result = tmp2[0] - '0';
    char* p = tmp2+1;
    while(*p)
    {
        if ((INT_MAX / 10) < result)
        {
            printf("oh dear: %d can't be reversed to int\n", n);
            exit(1);
        }
        result = result * 10;
        if ((INT_MAX - (*p - '0')) < result)
        {
            printf("oh dear: %d can't be reversed to int\n", n);
            exit(1);
        }
        result += *p - '0';

        p++;
    }

    return result;
}

int main()
{
    printf("Output: %d\n", reverse(123));
    printf("Output: %d\n", reverse(123456789));
    printf("Output: %d\n", reverse(1234567899));
    return 0;
}

Output:

Input : 123
Output: 321
Input : 123456789
Output: 987654321
Input : 1234567899
oh dear: 1234567899 can't be reversed to int

chux · Accepted Answer · 2020-04-25 00:54:52Z

But it gives runtime error on line sum=sum+rem*10;.

To test for potential int overflow of positive sum, rem, compare against INT_MAX/10 and INT_MAX%10 beforehand.

    if (sum >= INT_MAX / 10 && (sum > INT_MAX / 10 || rem > INT_MAX % 10)) {
      // overflow
    } else {
      sum = sum * 10 + rem;
    }

Handling negatives

Watch out for x = INT_MIN ... x = -x;. That is int overflow and undefined behavior.

Sometimes it is fun to solve such int problems of positive and negative numbers by converting the positive numbers to negative ones embrace the dark side - its your only hope. (maniacal laughter)

There are more int values less than zero than there are int values more than zero - by one. So x = -x is always well defined when x > 0.

// C99 or later code
#include <limits.h>

int reverse(int x) {
  int x0 = x;
  if (x0 > 0) {
    x = -x;  // make positive values negative, embrace the dark side
  }
  int reversed = 0;

  while (x < 0) {
    int rem = x % 10;
    x /= 10;
    if (reversed <= INT_MIN / 10
        && (reversed < INT_MIN / 10 || rem < INT_MIN % 10)) {
      // overflow
      return 0;
    }
    reversed = reversed * 10 + rem;
  }

  if (x0 > 0) {
    if (reversed < -INT_MAX) {
      // overflow
      return 0;
    }
    reversed = -reversed;
  }
  return reversed;
}

Test code

#include <stdio.h>

int main() {
  int x[] = {0, 1, -1, 42, 123456789, INT_MAX/10*10+1, INT_MIN/10*10-1,INT_MAX, INT_MIN};
  size_t n = sizeof x / sizeof x[0];
  for (size_t i = 0; i < n; i++) {
    printf("Attempting to reverse %11d ", x[i]);
    printf("Result %11d\n", reverse(x[i]));
  }
}

Sample output

Attempting to reverse           0 Result           0
Attempting to reverse           1 Result           1
Attempting to reverse          -1 Result          -1
Attempting to reverse          42 Result          24
Attempting to reverse   123456789 Result   987654321
Attempting to reverse  2147483641 Result  1463847412
Attempting to reverse -2147483641 Result -1463847412
Attempting to reverse  2147483647 Result           0
Attempting to reverse -2147483648 Result           0

dbush · Accepted Answer · 2020-04-24 14:49:04Z

2

First, you should not be defining your own values for INT_MAX and INT_MIN. You should instead #include <limits.h> which defines these value.

Second, this:

sum > INT_MAX

Will never be true because sum can never hold a value larger than INT_MAX. So you can't perform an operation and then check afterward if it overflowed. What you can do instead is check the operation first and do some algebra that prevents overflow.

if ( INT_MAX / 10 < sum) return 0;
sum *= 10;
if ( INT_MAX - rem < sum) return 0;
sum += rem;

edited Apr 24, 2020 at 14:49

user3657941

answered Apr 24, 2020 at 14:47

dbush

233k27 gold badges261 silver badges334 bronze badges

Collectives™ on Stack Overflow

Reverse integer in c gives overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related