Leetcode Question: Reverse integer

welcome to Jax problem-solving channel today we'll be going over the reverse integer problem it's a programming problem where the input is any given integer positive or negative and the output should be the reverse of this integer without the digits reversed in order it sounds like it's an easy thing to for humans to do but for a computer to do it we have to be careful how exactly we implement this code so let's get into the details so the problem statement just to reiterate is given an integer return the reverse whenever a given a problem I always like to draw a figure to represent the problem so in this case the figure is fairly straightforward but in the future we'll be solving more complex problems with multiple inputs and there could be multiple dependencies but in this particular problem the input is just an integer input X and the output is another integer but we reversed the caveat is that when the overflow occurs a specification for this function is that we should return zero in this case so this diagram captures it is the essence of this problem now let's dive into the details of how reverse is implemented before we implement the reverse function we should have an idea in our mind how it will be implemented so to do that I usually like to draw an example so in this case suppose the integer itself is 7 9 to 8 well if we wanted to reverse it for humans it's fairly easy we just write out the 8 - 9 7 and to reversed but for computers to do it there has to be a methodology for doing this so the computer should follow some the algorithm the computer can follow can be along the same lines that what humans do so for example first we pick out the first digit 8 and then the next digit 2 then the 9 and 7 then it's done so how is this done well we can use two variables to track the progression and in each iteration of the loop we can reduce the problem size so in the first iteration of the loop we can keep our reverse number we can set that to zero where as the input is the input integer X 7 9 2 8 so in the first iteration of the loop we should pick out the eight and store that in the reverse number eight and but we at the same time we need to reduce the problem size to ensure that when we run this loop and x where n is the number of digits in this number we're going to finish the problem so once the eight is taken care of we should reduce the problem size by eliminating the age from the X in the next iteration of the loop we should move the two to the reverse number and it should be incremented so such that the two is added to the right side of this eight well on the right side the X the problem size is again reduced and this loop iterates until X becomes zero when x is zero this is an indication that our reverse function has completed its job and that we can return this value so this is how conceptually this problem is solved let's look at the rough code on how this can be implemented so this is not the complete code but it captures the essence of how reverse is implemented so first we set reverse equal to 0 and in the loop while X is not equal to zero we should do a few things first we should pick out the the least significant digit of the input X and that's done by the remainder function so this remainder function when we call remainder 10 this picks out the least significant digit which I call pop here and then the X itself is reduced by removing the least significant digit this is done by using the divide by ten function in addition to this we need to check for overflow but I'll explain this part a little bit later so once we have the least significant digit we need to think about how to combine the least increment digit and the remainder of the x2 increment this loop so that's done by this line so the previous remainder is a multiplied by 10 this is ensure that there won't be any collision when we add in the new the new digit so in the case as above if you remember in order to add the two the previous eight we have to multiply by tenth to make it 80 so that we can add the two that's essentially what this line does so that the reverse number is updated by the previous reverse number multiplied by ten and adding the new digit so essentially this is how the reverse code is implemented so what about this overflow check that ye that I have loved space for here well to understand this first we need to discuss what is an integer and how is it represented so the way an integer is defined is it's a 32-bit representation what this means is that the integer that for any given integer number it's actually represented by a string of zeros and ones and there's this exactly 32 of them so for example 0 1 0 1 1 0 1 1 0 1 0 1 dot dot dot dot and then a string of 32 of them make up an integer because each digit you only have a choice of either 0 or 1 the maximum integer that's represented by a 32-bit storage is 2 to the 31 minus 1 the most negative integer that you can get is negative 2 to the power of 31 without this minus 1 so if you do the math the maximum integer that can be possibly represented is this number well the minimum integer that you can represent with 32 bits is this number it's different by one one might ask why is the max different by one compared to the minimum the reason is that it's not symmetric because you need to include zero and zero by definition is stored with the maximum so if this is a little bit confusing here's an example to explain if we only had three bits to represent a number and using if we use two's complement so that we can represent both positive and negative number so if we only have three bits there are eight possible numbers because to the power of three is eight so the numbers that are represented is - 4 - 3 - 2 - 1 and 0 1 2 3 so here as you can see the most negative number is minus 4 while the most positive number is minus 3 and here's a bit representation 4 - 4 - 3 using 3 bits the same logic applies to the case for real integers which are represented using 32 bits why is this important for this particular problem it's because when when the input is an integer when you reverse it it's possible that the reverse number is larger than the max number that can be represented using the integer format so in which case when we detect such a condition we should return 0 so how do we know when the integer will exceed the max let's take a look at the code so here's the complete code written in Java for the reverse function the input is an integer we set the reverse to zero and we loop through the integer we process one digit at a time starting from the least significant digit and we we decrease the problem size by dividing by 10 each time when this becomes zero that means you have processed your entire but digit and you can return the result now in terms of the air check the most critical line is this particular line where you're multiplying the previous result by 10 and adding the least significant digit so this multiplied by 10 it's possible for you to go over your max integer storage space so we have we added a check for that so for example if the max in if this previous reversed result is already greater than one-tenth of the max integer when you multiply by 10 it will go over the int max number this int max is the constant it this is equal to 2 to the power 31 minus 1 as explained on the previous slide or if the previous reverse number is equal to int max divided by 10 and the least significant bit is greater than 7 then you will also go over in the max why is why is there a greater than 7 you ask well it's because the int max I'll just write it here int max it's equal to 2 1 4 7 4 8 3 6 4 7 so here's where the 7 becomes critical if the if this previous reverse number is exactly equal to the into by by 10 but the least significant bit is less than or equal to 7 it's still okay because you can still represent that as an integer but if it's greater than 7 and this is equal to 1/10 of the N max then you will overflow so the same logic applies to the negative case so we checked the positive case we checked the negative case and we apply the updated result in the while loop and then we return the result how does it work for negative numbers you ask well it turns out that the remainder function in Java or C++ also works for negative numbers so for example if your input was negative 328 and you apply the remainder function of 10 the result would give you minus 8 so the code does not need to be changed and you can directly run this code for positive or negative numbers and the result should be correct try it for yourself the end

Channel: Problem Solving for Fun

Views: 2,624

Rating: 4.8965516 out of 5

Keywords:

Id: VxN5xisdvOs

Length: 11min 31sec (691 seconds)

Published: Sun Jan 27 2019