Create a resume that lands you SDE interviews at MAANG

Speaker

Anubhav Sinha

SDE-2 @

12 Jun, 2024 @ 01:30 PM

Introduction

Suppose you are in a coding interview and given a problem. You provided the right solution to the problem. After seeing your solution, interviewers can ask you to optimize it in terms of time or space complexity if they know any optimization can happen.

You must prepare yourself thoroughly for every problem so that you do need to face the consequences of not optimizing the solution. In this blog, we will optimize a famous problem in the world of programming.

Problem Statement

We will be given a number, and the task is to determine whether the given number is a palindrome. A number is considered a palindrome if the reverse of the number is the same as the original number.

Example

Input

Number = 1441

Output

Yes, the given number is a palindrome.

Input

Number = 4432

Output

No, the given number is not a palindrome.

There is a condition for the given problem statement. The palindrome problem is famous, so there are multiple approaches to solving it. Our task is to check the palindrome without using any extra space.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach 1

To avoid using extra space, we can compare the number's left and rightmost digits. If both digits are the same at every iteration we do after reducing the number until the number is zero, then the given number is a palindrome.

To compare the digits, we need to extract them from the number, so first, we will find the divisor for the number, then we will compare the extracted digits and check if it is a palindrome.

Algorithm

Check if the given number is negative. If yes, return false.

Also, check if the given number is less than 10. If yes, then return true.

Calculate the divisor for the number.

Calculate the leftmost digit using (number/divisor).

Calculate the rightmost digit using (number%10).

If both are the same, extract the digits using ‘number = (number%divisor)/10’. And reduce the divisor.

Return false if digits are not the same.

Repeat steps 4 to 7 until the number is zero.

Return true.

DRY Run

Number = 1441

First, we must find the divisor to divide the given number and calculate the palindrome. The divisor should be 10^((total digits in number)-1). In this case, it is 1000.

Now we will extract the left and right most digit from the given number.

We can calculate the left-most digit by the formula:(number/divisor) and the right-most digit by: (number%10).

Left-digit = 1441/1000 = 1.

Right-digit = 1441%10 = 1.

Both are the same, so we will remove these numbers using number = (number % divi) / 10.

number = (1441%1000)/10 = 44.

We must change the divisor again using the formula divisor = divisor/100. Our new divisor will be 10 because divisor = 1000/100 = 10. Again check the left and right most digit.

Again both digits are the same.

Left-digit = 44/10 = 4.

Right-digit = 44%10 = 4.

Our given number after the above comparison will be zero because number = (44%10)/10 is 0. This means the given number is a palindrome.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Function to check number is palindrome or not.
bool checkPalindrome(int number) {
// Returning false if number is negative.
if (number < 0) {
return false;
}
// Returning true if number is single digit.
if (number < 10) {
return true;
}
// Calculating total digits in the number.
int divi = to_string(number).length();
// Calculating divisor.
divi = pow(10, divi - 1);
/*
Calculating and comparing the right and left
most digit until given number is greater than 0.
*/
while (number > 0) {
int leftMostDigit = number / divi;
int rightMostDigit = number % 10;
if (leftMostDigit == rightMostDigit) {
number = (number % divi) / 10;
divi = divi / 100;
} else {
return false;
}
}
return true;
}
int main() {
bool result = checkPalindrome(1441);
if (result) {
cout << "Yes, the given number is a Palindrome";
} else {
cout << "No, the given number is not a Palindrome";
}
return 0;
}

Output

Implementation in Python

# Function to check number is palindrome or not.
def checkPalindrome(number):
# Returning false if number is negative.
if number < 0:
return False
# Returning true if number is single digit.
if number < 10:
return True
# Calculating total digits in the number and divisor.
divi = pow(10,len(str(number))-1)
# Calculating and comparing the right and left most digit
# until given number is greater than 0.
while number > 0:
leftMostDigit = number //divi
rightMostDigit = number % 10
if(leftMostDigit == rightMostDigit):
number = (number%divi) //10
divi = divi //100
else:
return False
return True
result = checkPalindrome(1441)
if result:
print("Yes, the given number is a Palindrome")
else:
print("No, the given number is not a Palindrome")

Output

Complexity Analysis

The time complexity for the above solution is O(N/2), where ‘N’ is the total digits in a given number. We will loop N/2 time to calculate and compare the digits, that are why the time complexity is O(N/2).

The space complexity for the above solution is O(1). We have not used extra space to store the exact number in another variable. We have performed the operations on the input variable, so our space complexity will be O(1).

In the second approach, we will divide the given number into two halves and compare both halves with each other. If both are the same, it is a palindrome number as it reads the same forwards as backward; otherwise, it is not a palindrome number.

We will divide the given number by 2, but first, we need to count the number of digits in the given number. The number of digits can be even or odd, then do the following accordingly

Even: Split it into two halves.

Odd: Remove the last number from the first half of the number.

Algorithm

If the given number is negative, return false.

If the given number is less than 10, return true.

Create a digits variable and store the number of digits in it.

Create a half variable to store the second half number and initialize it with zero.

Run a loop wherein split = split * 10 + number%10 and number = number/10; it stores the second half number in the reversed form in the half variable.

The second half number is stored in the half variable, and the first half is stored in n.

If the number of digits is odd, remove the last number from the first half.

Finally, check whether the first half equals the second half. If both are equal, return true.

In the end, return false.

DRY Run

Number = 1441

The number 1441 is neither negative nor smaller than 10, so we can perform our operations on it.

First, we will calculate the total digits in the given number. Here we will use the count variable to store the total digit. The count will be 4.

Now we will loop count/2 = 4/2 = 2 times to split the given number into two halves. We will store the given number in split and number variables.

split = split*10 + number%10 where the split will be initialized as 0.

number = number/10.

First loop

split = 0*10 + 1441%10.

number = 1441/10.

split = 1.

number = 144.

Second loop

split = 1*10 + 144%10.

number = 144/10.

split = 14

number = 14

Now, before comparing, we will check whether the count is odd. If it is odd, we will perform one more operation of split = split*10 + number%10 to balance out the digits. Here we do not have to because the count is even.

Compare split and number variables. Both split and number variables are equal means the given number is a palindrome.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Function to check given number is Palindrome or not.
bool checkPd(int number) {
// Returning false if number is negative.
if (number < 0)
return false;
// Returning true if number is single digit.
if (number < 10)
return true;
// Calculating total digits in given number.
int count = to_string(number).length();
int split = 0;
int temp = 0;
// Spliting the number until temp is less than count/2.
while (temp != count / 2) {
split = split * 10 + number % 10;
number = number / 10;
temp++;
}
// If the count is odd, add one more digit in split.
if (count % 2 != 0)
split = split * 10 + number % 10;
// If split is equal to number return true.
if (split == number)
return true;
return false;
}
int main() {
if (checkPd(1441)) {
cout << "Yes, the given number is a Palindrome";
} else {
cout << "No, the given number is not a Palindrome";
};
}

Output

Implementation in Python

# Function to check given number is Palindrome or not.
def checkpd(number):
# Returning false if number is negative.
if(number < 0):
return False
# Returning true if number is single digit.
if(number < 10):
return True
# Calculating total digits in given number.
count = len(str(number))
split = 0
temp = 0
# Spliting the number until temp is less than count/2.
while(temp!=count//2):
split = split*10 + number%10
number = number//10
temp = temp+1
# If count is odd adding one more digit in split.
if(count%2!=0):
split = split*10 + number%10
# If split is equal to number return true.
if(split==number):
return True
return False
if __name__ == "__main__":
if(checkpd(1441)):
print("Yes, the given number is a Palindrome")
else:
print("No, the given number is not a Palindrome")

Output

Complexity Analysis

The time complexity for the above solution is O(N/2), where ‘N’ is the total digits in a given number. We will loop N/2 times to calculate and compare the digits, so the time complexity is O(N/2).

The space complexity for the above solution is O(1). We have not used extra space to store the exact number in another variable. We have performed the operations on the input variable, so our space complexity will be O(1).

If the reverse of a number is the same as the original number, then it is a palindrome number. For example, 1221.

What is pow()?

We can measure the power of a number using the pow() function.

What is a divisor?

The number which divides the given number is known as the divisor.

Is a single-digit number a palindrome or not?

Yes, every single-digit non-negative number is a palindrome.

What is the to_string() function?

To convert a data type into a string data type, we use the to_string() function.

Conclusion

In this blog, we discussed checking whether the given number is a palindrome without using extra space. We have implemented the solution in two programming languages.

Check out the following articles to learn more about problems.