all articles

2016-09-28

# 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. 