all articles

leetcode war 7 - Reverse Integer

2016-09-28 @sunderls

leetCode

leetcode war :Reverse Integer

https://leetcode.com/problems/reverse-integer/

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321

Analysis

for 123, we can get the least significant digit every time, and accumulate the result, by following

  1. 123 -> 12, result -> 3
  2. 12 -> 1, result-> 3 * 10 + 2
  3. 1 -> 0, result -> 32 * 10 + 1 = 321

about the sign, we keep a flag at first.


var reverse = function(x) {
    var result = 0;
    var rest = x;
    var flag = 1;

    if (x < 0){
        flag = -1;
        x = -1 * x;
    }

    while(x > 0){
        rest = x % 10;
        result = result * 10 + rest;
        x = Math.floor(x / 10);
    }

    return flag * result;
};

While this is almost right, but it turned out that if we reverse an integer it may overflow. we have to add some boundary check.

var reverse = function(x) {
    var result = 0;
    var rest = x;
    var flag = 1;

    var MAX_INT = Math.pow(2,32 - 1) - 1;
    var MIN_INT = - Math.pow(2,32 - 1);

    if (x < 0){
        flag = -1;
        x = -1 * x;
    }

    while(x > 0){
        rest = x % 10;
        result = result * 10 + rest;
        x = Math.floor(x / 10);
    }

    result = flag * result;
    if (result > MAX_INT || result < MIN_INT){
        return 0;
    } else {
        return result;
    }
};

This passed, but too slow, ranking at the last 12%, 179ms.

Improvements

There is no editorial solution on leetcode, but I found an article here: http://www.programcreek.com/2012/12/leetcode-reverse-integer/. Which told me that I didn't need to handle the sign problem, since -11 % 10 === -1, thus came the following improvements:

firstly, we change the last if conditions to ternary operator: 122ms, 86% then, we remove the sign handling, which has much cleaner code.

var reverse = function(x) {
    var result = 0;
    var MAX_INT = Math.pow(2,32 - 1) - 1;
    var MIN_INT = -Math.pow(2,32 - 1);

    while(x !== 0){
        result = result * 10 + x % 10;
        x = (x / 10) | 0;
    }
    return (result > MAX_INT || result < MIN_INT) ? 0 : result;
};

There is no integer in javascript, so to truncate the decimal part, we can use bitwise or | 0. how does this work? sorry to forgot almost all of college study.

According online(http://stackoverflow.com/questions/7487977/using-bitwise-or-0-to-floor-a-number), all bitwise operators work on 32-bit integers, and ecma spec says that binary operators will call ToInt32 to convert values to signed 32-bit integers http://ecma262-5.com/ELS5_HTML.htm#Section_11.10. So it works.

Besides | 0, we can also use Math.trunc()

About MAX_INT and MIN_INT

what is the largest and smallest 32-bit integer? I didn't get right answer until searching for the detail explanation, here I'll leave some of my understandings.

  1. as we know, computers store data in bits, take a 3-bit as an example:
  2. 000 must be 0, no doubt, 001 => 1, 011 => 3, this have no problem. what about a negative number? a positive number, if added to its negative counterpart, will result in 0, so for 3 (011), -3 should be (101), in fact the result is 1000, overflowed. So the negative number is got by reversing the bits & plus 1
  3. for a negative number, the highest bit must be 1, because it have to give a carry to 1000 when added to positive counterpart, respectively, positive numbers start with 0
  4. so the max positive number is 011 => 3, -3 is 101, -2 is 110, -1 is 111. here is natural thought 100 is -4.
  5. so the range should be [-2^(n-1), 2^(n-1) -1], since 0 has no sign, signed numbers & unsigned numbers have the same account.