We have been given a signed 32-bit integer & we need to return the reverse of it.
if input_x = 345 return output_x = 543 if input_x = -345 return output_x = -543
My Thought About Solution
- At first glance, the answer looks pretty straightforward. we just convert integer to string, then read each character and append it to the output string.
- But we quickly realize that if we do so we also have to handle signs.
That’s easy we can write code to take the first character as a substring from input and if it is a sign we can prepend to the reversed string.
- Of course, we have to parse the to and from between integer and string
input_x = 345 output_x = 543input_x = -345 output_x = 543- // oops we need to handle sign as well .
- So, looks like we have a solution. Easy code!
- But I forgot that reversed input can also fall outside of the range [-2³¹,2³¹-1], that case we need to handle.
- if reverse integer falls out of range [-2³¹, 2³¹-1], then we need a data type that can store bigger integer than 32 bit. I think a long data type can store that integer since it’s 64 bit long.
- So while parsing from reversed input string to long we will not get an exception for the reverse integer which falls out of the range [-2³¹, 2³¹-1].
Data structure: We are not using any collection, just primitive types integer, long, string, etc.
Time-complexity: O(length(N)) where N is the input integer
Space-complexity: O(1) constant space
1: Get the sign of the input integer (if it is - integer) . We will append it to our result integer. 2: convert integer input to long input 3: get the absolute value of long input ( avoiding - sign) 4: get the string value of long input 5: reverse the long input and get the reversed string input 6: convert reversed string input to long input 7: check if the long input is greater than max val of 32-bit integer if yes then return 0 else return integer value with sign
- Our submission beats just 7% of java submissions. Not that impressive. So I need to modify the solution.
- In solution, I believe a lot of time is spent in parsing to and from between long, string, and integer.
- So in our modified solution, this has to be minimum.
- Can we achieve our result without converting the integer to string? can we just use integer and reverse it. Turns out that we can.
- We can just use the same logic that we used on a string on our integer input which saves our runtime by avoiding integer to long to string etc..
Our result is very impressive this time. Runtime beats 100% of the submission. Nice job!
This Leetcode is good problem to understand
- Typecasting In Java,
- Max, and min value handling of integer
- How to iterate over each digit in integer and play around with it.
Let me know if you have some opinion on the solution in the comment!
- If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )