Reverse a Number
Given an integer num, reverse the digits of the number and return the reversed number.
Examples
Input: 687
Output: 786
Explanation: If we reverse the number 687, we will get 786.
Input: 120
Output: 21
Explanation: If we reverse the number 120, we will get 021 so after removing trailing zeroes we get 21.
Intuition
Before this question, we knew exacting the digits from a number.
Now in this question, we are told to reverse a number, So could extracting the digits from the number help us in any way?
Yes, it will!
If you closely observe, extracting the number we were getting the last digit at first, then the second last digit, then the third last digit, and so on till the first digit.
Now after extraction of digits, we know we are getting the digits in the reverse order of the initial number, so now we just have to combine those extracted digits to form a new number which is the reverse of the initial number.
So how will we be doing that?
Let us understand it with an example where the number is 123.
We can write 123 as 1*(10^2) + 2*(10^1) + 3*(10^0) (So 1 is in the hundred places, 2 is in the tens place and 3 is in one's place)
Now after the extraction of the digit, the digits are in order 3 2 1, so we just have to combine them to form the reverse, to do so we will simply multiply 3 with the most significant power, 2 with the 2nd most significant power, and then with 1.
So it will be like 3*(10^2) + 2*(10^1) + 1*( 10^0) = 321.
Now we can say we can form the reverse number of a number by combining the extracted digits by multiplying each one of them to the power of 10 (higher to lower) and summing them up.
In general, the formula is,
di is the i-th digit of the number N when reading from right to left (starting from the least significant digit).k is the total number of digits in N minus 1.
So, this is one of the methods we can follow, where we multiply the last digit with 10^k, and the second last digit with 10^(k-1) …. and so on. For this method, we need to count the length(k) of the given number first and then do the operations that we have discussed.
So this method needs an extra space to store the extracted digits so to avoid this extra space we can create the reverse number in a single pass during extracting only.
Approach
To reverse a number, start by initializing reversedNumber to 0. Then, repeatedly extract the last digit of num by finding the remainder when num is divided by 10. Update reversedNumber by multiplying it by 10 and adding the extracted digit. Next, remove the last digit from num by dividing it by 10. Continue these steps until num becomes 0. At the end of this process, reversedNumber will contain the reversed form of the original number.
Let's understand it with an example for num = 12345
Initially num = 12345 and reversedNumber = 0.
num is in the decimal number system (Base 10).
At the first iteration, if we divide the number by 10 we get the quotient as 1234 and the remainder as 5 (last digit of 12345).
num = 1234 and reversedNumber = reversedNumber * 10 + 5 = 5.
Now at the second iteration, if we divide the number by 10 we get the quotient as 123 and the remainder as 4 (last digit of 1234).
num = 123 and reversedNumber = reversedNumber * 10 + 4 = 5*10 + 4 = 54.
Now at the third iteration, if we divide the number by 10 we get the quotient as 12 and the remainder as 3 (last digit of 123).
num = 12 and reversedNumber = reversedNumber * 10 + 3 = 54*10 + 3 = 543.
Now at the fourth iteration, if we divide the number by 10 we get the quotient as 1 and the remainder as 2 (last digit of 12).
num = 1 and reversedNumber = reversedNumber * 10 + 2 = 543*10 + 2 = 5432.
Now at the fifth iteration, if we divide the number by 10 we get the quotient as 0 and the remainder as 1 (last digit of 1).
num = 0 and reversedNumber = reversedNumber * 10 + 1 = 5432*10 + 1 = 54321.
Now since our num has become 0, dividing it with 10 will keep giving us a remainder 0 for infinite times, so there is no sense of dividing it anymore and getting the remainder.
So our loop should terminate, Exit.
Code Implementation
C++ Code Try on Compiler!
int reverseNumber(int num) {
int reversedNumber = 0;
while (num > 0) {
// Extract the last digit
int digit = num % 10;
// Build the reversed number
reversedNumber = reversedNumber * 10 + digit;
// Remove the last digit
num = num / 10;
}
return reversedNumber;
}Java Code Try on Compiler!
public class ReverseNumber {
public static int reverseNumber(int num) {
int reversedNumber = 0;
while (num > 0) {
int digit = num % 10;
reversedNumber = reversedNumber * 10 + digit;
num = num / 10;
}
return reversedNumber;
}
}
Python Code Try on Compiler!
def reverse_number(num):
reversed_number = 0
while num > 0:
digit = num % 10
reversed_number = reversed_number * 10 + digit
num = num // 10
return reversed_numberJavascript Code Try on Compiler!
function reverseNumber(num) {
let reversedNumber = 0;
while (num > 0) {
let digit = num % 10;
reversedNumber = reversedNumber * 10 + digit;
num = Math.floor(num / 10);
}
return reversedNumber;
}Time Complexity : O(logn)
The time complexity arises from the number of digits in the number. The number of times the while loop runs depends on the number of digits in the given number num.
For a given number num in a decimal representation, the number of digits is approximately equal to log10(num). This is because each digit represents a power of 10.
The loop executes once for each digit in num.
Therefore, the loop runs log10(num) times, which simplifies to O(logn).
Space Complexity : O(1)
We are using only variables like reversedNumber, and digits that use constant space.
Since the space required by these variables does not depend on the size of the input number num, the auxiliary space is O(1).
Now Since we have learned about how to reverse a number, let's solve another problem using the same concepts that we have learned before to check if a given number is palindrome or not.