Hey all! Today we are solving a LeetCode Easy problem. I know it's an easy one but I learned something new while solving this one so stay tuned for that! Let's get into the problem right away.

Problem

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example: 
Input: x = 123
Output: 321

Solution

Okay for this problem, I want to show you only one solution as I was happy with my first one and did not want to code another one. Let's see the code and then we'll discuss it line by line.

class Solution {
public:
    int reverse(int x) {
        long y = x;
        int coef = 1;
        if (y < 0) {
            coef = -1;
            y = y * -1;
        }
        long rev = 0;
        while(y > 0) {
            if (coef * rev * 10 > INT_MAX || coef * rev * 10 < INT_MIN) {
                rev = 0;
                break;
            }
            int digit = y % 10;
            rev = rev * 10 + digit;
            y = y / 10;
        }
        return rev * coef;
    }
};

Okay, so at first we declare a variable called y to store the value of x. I intentionally used long instead of int for y and will see the reason ahead in the code. Then I declare and initialize a variable called coef to just know if the number is positive or negative. In the next 4 lines, I just do that, if y is negative I set coef to -1 and make y a positive number by multiplying it with -1.

After that, I declare a variable called rev which will store the reversed number. Both of these variables(y and rev) are long because when I get a number like -2147483648 in x, an int can handle that but it can not handle the positive version of this number which is 2147483648 because an integer can only store up to the number 2147483647. So y = y * -1 would fail so I decided to use long for y. In the case of rev, rev * 10 in the code would sometimes cross the limit of an integer so I changed that to a long as well.

Then comes the while loop which is pretty simple, It's a cheap rip-off of palindrome check for numbers lol. At first, I am just checking if the current rev multiplied by 10 and its coef exceeds the integer limit or not. If so I am just setting rev to 0 and returning that or else I continue with the current rev. Then by doing y % 10 I am getting the last digit of the number(try that out!). Then I am adding the digit(y) and to the end of rev.

For example, if rev is 12 and y is 3.

// rev = rev * 10 + y
rev = 12 * 10 + 3

So, rev is now 123. Hence adding 3 after 12.

Then comes y = y / 10, Here is what this line is doing. y is a long and not a float. And let's say y is 123. So y / 10 is equals to 12.3. But we are storing the result(12.3) back in y which is a long so only the integer part of 12.3 will be stored which is 12 so after this line y becomes 12. For the last integer, let's say y = 1 now. y / 10 would be 0.1 and the integer part is 0. This explains the condition for the while loop to stop which is y > 0. So the while loop will stop at the end of the last digit.

After the while loop ran, we have our number reversed. Then we just need to multiply coef to it. So that the number would be negative if the number initially was negative and vice-versa. So we return coef * rev.

With that, the algorithm is done. And then as usual I check the official solutions and other solutions in the discussions tab. And I found one similar to mine but a lot cleaner. Mine was already faster than 100% so I wasn't really checking for better solutions but I still took this cleaner code and ran it. It got accepted but It wasn't as fast as mine but I wondered why, since it was pretty similar to mine. The only difference was the if sentence inside the while loop. Here's their if sentence. Try to spot the difference.

if(rev > INT_MAX/10 || rev< INT_MIN/10)

Did you see it? (yes Nukes Top 5 reference!). The difference is they were dividing and I was multiplying. They were doingINT_MAX/10 and I was doing rev * 10. So I thought, is division a more expensive operation than multiplication? Maybe yes! Why? Let's find out!

Why is division a more expensive operation than multiplication?

There is a quite complex and more technical explanation for this But I will just pick the easy route. In layman's terms division is a more expensive algorithm because division algorithms can't be parallelized as efficiently as multiplication algorithms so it requires more clock cycles which in simple terms means IT JUST NEED MORE TIME.

So I guess that's why our time complexities differ. I didn't know this before and I thought it's a good thing to keep in mind while crafting algorithms. So I put this article together.

See you in the next one!