Оффлайн
- Регистрация
- 9 Май 2015
- Сообщения
- 1,483
- Баллы
- 155
Hello there! Continuing with this series about the 10 most common algorithms asked in technical interviews. Today we'll examine another frequently requested algorithm. Since it's quite similar to our previous , I'm going to add a small twist: instead of working with strings, let's check if a number is a palindrome.
Following the structure of my previous article, I'll first explain the problem statement, then walk through the algorithm, and finally show the implementation.
What is a palindrome
By definition, a palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. In other words, a palindrome remains unchanged when its characters are reversed.
A common example in Spanish is anita lava la tina. For English speakers, a similar palindrome is was it a car or a cat I saw.
When dealing with numbers, a typical example is 121.
If you've read my , you already know how to reverse a string, which gives you half the solution.
Problem Statement
The problem statement has already defined the input (an integer) and the output (a boolean). Now, let's outline the step-by-step process to convert this input into the expected output.
Algorithm to Solve it
There are two approaches to solving this in JavaScript. You already know how to (the first approach), so let's explore the second approach: the mathematical solution.
Since the input is an integer, we may receive a negative number. The first step is to get the absolute value of the input. JavaScript provides a helper function for this in the .
- Initialize a variable temp to the input number and get its absolute value.
let temp = Math.abs(num);
- Then, initialize a variable called reversed to 0 and a constant called original to store the initial value.
let reversed = 0;
const original = temp;
Next, we need to iterate through our number to determine if it's a palindrome. For this, we'll use a simple while loop.
- While the number (temp) is greater than 0:
while(temp > 0){
const digit = temp % 10;
reversed = reversed * 10 + digit;
temp = Math.floor(temp / 10);
}
Inside the loop we are:
Getting the last digit of the number using the (%) to extract the remainder when dividing the temp variable by ten.
Building our reversed number by multiplying the current value of reversed by 10 and adding the extracted digit.
Removing the last digit from temp by using on the result of dividing temp by ten.
In each iteration, we remove the last digit from the temp variable (which initially holds our input value) and build the reversed number by adding digits in reverse order. Once temp becomes 0 as a result of the Math.floor division, the loop terminates.
Our final step is to compare the initial value stored in the original constant with the reversed value stored in the reversed variable that we built during our loop.
- Compare original to reversed: If they are equal, return true; otherwise, return false.
return original === reversed;
Algorithm Using an Example
To better understand this algorithm, let's walk through it step-by-step using -121 as our example input.
- Initialize a variable temp to the input number and get its absolute value.
let temp = Math.abs(num); // temp = 121
- Initialize a variable called reversed to 0. And a constant with the original value.
let reversed = 0;
const original = temp; // original = 121
- While the number (temp) is greater than 0:
Get the last digit of the number using the reminder operator to get the result of dividing the temp variable between ten.
Adding this digit to reversed (multiplying reversed by ten and adding the last digit).
Finally, removing the last digit from the number using Math.floor and dividing by ten the temp variable.
Let's walk through the first iteration:
while(temp > 0){ // temp = 121
const digit = temp % 10; // 121 % 10 = 1
reversed = reversed * 10 + digit; // 0 * 10 + 1 = 1
temp = Math.floor(temp / 10); // Math.floor(121 / 10) = 12
}
Now temp equals 12, so the loop continues. The second iteration is:
while(temp > 0){ // temp = 12
const digit = temp % 10; // 12 % 10 = 2
reversed = reversed * 10 + digit; // 1 * 10 + 2 = 12
temp = Math.floor(temp / 10); // Math.floor(12 / 10) = 1
}
Now temp equals 1, so the loop continues. The third iteration proceeds as follows:
while(temp > 0){ // temp = 1
const digit = temp % 10; // 1 % 10 = 1
reversed = reversed * 10 + digit; // 12 * 10 + 1 = 121
temp = Math.floor(temp / 10); // Math.floor(1 / 10) = 0
}
Finally, temp equals 0, so the loop breaks and we have our reversed integer. Now, let's compare the initial value stored in the original constant with the reversed number.
return original === reversed // 121 === 121: returns true
Since 121 equals 121, our function returns true.
Bonus track: Using Strings and Arrays
In JavaScript, we can also solve this problem by converting the number to a string and then using the to compare the original with the reversed version.
Here's how the string-based algorithm works:
- Initialize a constant str that stores the absolute value of the number converted to a string.
const str = Math.abs(num).toString();
- Convert the string to an array, reverse the array, and convert it back to a string.
const reversedStr = str.split('').reverse().join('');
- Compare the original string with the reversed string
return str === reversedStr;
And that's it. We've solved the problem using arrays and strings. This solution is simpler and more readable with small numbers like our example input 121, but for larger numbers, the mathematical approach is actually better since it doesn't create additional objects (strings and arrays).
Typescript implementation
Using the mathematical approach (digit-by-digit reversal):
function isPalindrome(num: number): boolean{
let temp = Math.abs(num);
const original = temp;
let reversed = 0;
while(temp > 0){
const digit = temp % 10;
reversed = reversed * 10 + digit;
temp = Math.floor(temp / 10);
}
return original === reversed;
}
Using the string and array approach:
function isPalindromeString(num: number):boolean{
const str = Math.abs(num).toString();
const reversedStr = str.split('').reverse().join('');
return str === reversedStr;
}
Conclusion
Finally, let's analyze both approaches to check if an integer is a palindrome, since we already know :
The mathematical approach has a time complexity of O(n), where n is the number of digits, and a space complexity of O(1) because it only uses primitive variables, resulting in minimal memory usage.
The string and array approach also has a time complexity of O(n), but it performs more expensive operations by manipulating additional objects. This becomes significant with larger inputs. Its space complexity is O(n) since it creates additional objects that require extra memory.
While one-liners are often more elegant than multi-line solutions, remember that platforms like LeetCode include hidden tests with larger inputs where performance matters. The more efficient mathematical approach will earn you a higher score.
Remember you can review the code for this and other algorithms in my GitHub repo:
Keep practicing, and see you in the next article!