My solution to Reverse Integer got AC, but in fact it was just correct on specific test cases.


  • 1
    S

    My first solution was as follows:

    class Solution {
    public:
        int reverse(int x) {
            char digits[11] = {0,0,0,0,0,0,0,0,0,0,0}, i;
            int weight = 1000000000, temp = x, retval = 0;
            if(x < 0){
                weight = -weight;
            }
            for(i = 1; i <= 10; i++){
                digits[i] = temp/weight;
                temp %= weight;
                if(i <= 9){
                 weight /= 10;
                }
            }        
            for(i = 1; i <= 10; i++){
                if(digits[i] != 0){
                    temp = retval;
                    retval += digits[i]*weight;
                    if(weight > 0 && retval < temp){
                        return 0;
                    }else if(weight < 0 && retval > temp){
                        return 0;
                    }
                }
                if(retval != 0){
                    weight *= 10;
                }
            }
            return retval;
        }
    };
    

    The solution once got AC, but after compared to the reference solution, I found they're not all the same. For overflow cases my solution generates wrong answers.
    Later I add some modifications to it, and it proves to be correct now.

    class Solution {
    public:
        int reverse(int x) {
            char digits[11] = {0,0,0,0,0,0,0,0,0,0,0}, i;
            int weight = 1000000000, temp = x, retval = 0;
            if(x < 0){
                weight = -weight;
            }
            for(i = 1; i <= 10; i++){
                digits[i] = temp/weight;
                temp %= weight;
                if(i <= 9){
                    weight /= 10;
                }
            }        
            for(i = 1; i <= 10; i++){
                if(digits[i] != 0){
                    temp = retval;
                    retval += digits[i]*weight;
                    if(i == 10 && digits[i] == 2){//bugs once found here and below
                        if(weight > 0 && retval < temp){
                            return 0;
                        }else if(weight < 0 && retval > temp){
                            return 0;
                        }
                    }else if(i == 10 && digits[i] > 2 && (weight == 1000000000 || weight == -1000000000)){
                        return 0;
                    }
                }
                if(retval != 0){
                    weight *= 10;
                }
            }
            return retval;
        }
    };

  • 0
    S
    This post is deleted!

  • 0
    S

    Appreciate your feedback!

    Your first code should be wrong answer now.

    Could you please attach the particular test case next time? It would be more convenient for us. Thanks.


  • 0
    S

    The idea is simple. I changed multiplication into addition. Because if 0 <= a, b <= INT_MAX and a + b < 0, there must be some thing happened ^~^

    class Solution {
    public:
        int reverse(int x) {
        
            if (x == INT_MIN) {
                return 0;
            }
            int _x = (x > 0 ? x : -x);
            
            int result = 0, pre = 0;
            
            while (_x != 0) {
               
                for (int i=0; i<9; ++i) {
                    result += pre;
                    if (result < 0) {
                        return 0;
                    }
                }
                result += _x % 10;
                if (result < 0) {
                    return 0;
                }
                
                _x /= 10;
                pre = result;
            }
            
            return (x > 0 ? result : -result);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.