# Conquering LeetCode #5

I’m going following the order of questions given on the LeetCode problems page. The next one on the list was Reverse Integer.

Reverse digits of an integer.

Example1:x = 123, return 321Example2:x = -123, return -321

Seemed basic enough, and it was for the most part. I tripped on detecting the overflow. I found myself getting too concerned about what the value of the maximum possible int was going to be. But then I realized I didn’t need to. I just needed to check if the value was so different that I couldn’t compare it to my previous value.

Here is what I came up with:

public class Solution {

public int reverse(int x) {

int result = 0;

int isNegative = 1;

if (x < 0){

x *= -1;

isNegative = -1;

}

while (x != 0){

int unit = x % 10;

int temp = result * 10 + unit;

if ((temp - unit) / 10 != result) {

return 0; // overflow detected

}

result = temp;

x /= 10;

}

return result * isNegative;

}

}

I ended up looking at the solution here, and realized it was very similar except without the isNegative int flag. Turns out the rest of the code can handle negative integers on its own so there’s no need for that extra int.

public class Solution {

public int reverse(int x) {

int result = 0;

while (x != 0){

int unit = x % 10;

int temp = result * 10 + unit;

if ((temp - unit) / 10 != result) {

return 0; // overflow detected

}

result = temp;

x /= 10;

}

return result;

}

}

—

The second problem I worked on today was String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint:Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes:It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

I was pleasantly surprised that this question somewhat built on the previous one. This time, I decided to keep the isNegative flag because I found it useful.

Oh and I did look at the hint to figure out the requirements for atoi.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

And again, the overflow/underflow thing tripped me. There was a lot of trial and error involved until I finally reached a solution that worked.

I realized that when I was reading numbers from the string, I was only reading them as positive. So the only way my ‘temp’ variable would be negative was if an overflow had occurred. If my temp variable was different from the previous result, that was also a sign of overflow.

After that, I needed to figure out if I had to return the MAX_VALUE or the MIN_VALUE. If the sign in the string was negative, then I’d return the MIN_VALUE because the number in the string was less than the minimum acceptable value, and vice versa.

public class Solution {

public int myAtoi(String str) {

str = str.trim();

int result = 0;

int start = 0;

int isNegative = 1;

if (str.length() > start){

if ((int) str.charAt(start) == 45 // negative sign

|| (int) str.charAt(start) == 43){ // positive sign

if ((int) str.charAt(start) == 45){ // if negative

isNegative = -1;

}

start = 1;

}

}

for (int i = start; i < str.length(); i++){

// if is valid integer

if ((int) str.charAt(i) > 47 && (int) str.charAt(i) < 58){

int unit = ((int) str.charAt(i)) - 48; // get integer value

int temp = result * 10 + unit;

if (temp < 0 || (temp - unit) / 10 != result){ // if overflow or underflow has occurred

if (isNegative == -1){

return Integer.MIN_VALUE;

}

return Integer.MAX_VALUE;

}

result = temp;

} else {

return result * isNegative;

}

}

return result * isNegative;

}

}

I’m sure I could make this code cleaner, but for now I’ll leave it as it is.