Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Implementation in Python
3.5.
Complexity Analysis
4.
Approach 2
4.1.
Algorithm
4.2.
DRY Run
4.3.
Implementation in C++
4.4.
Implementation in Python
4.5.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a palindrome number?
5.2.
What is pow()?
5.3.
What is a divisor?
5.4.
Is a single-digit number a palindrome or not?
5.5.
What is the to_string() function?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check if a number is a palindrome or not without using any extra space

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.

introduction image

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.

Check out the Palindrome Number blog for another approach.

Get the tech career you deserve, faster!
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

  1. Check if the given number is negative. If yes, return false.
     
  2. Also, check if the given number is less than 10. If yes, then return true.
     
  3. Calculate the divisor for the number.
     
  4. Calculate the leftmost digit using (number/divisor).
     
  5. Calculate the rightmost digit using (number%10).
     
  6. If both are the same, extract the digits using ‘number = (number%divisor)/10’. And reduce the divisor.
     
  7. Return false if digits are not the same.
     
  8. Repeat steps 4 to 7 until the number is zero.
     
  9. 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.

DRY Run example

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.
DRY Run example

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.

DRY Run example

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

C++ code 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

python code 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).

You can also read about Palindrome Number in Python and Euclid GCD Algorithm

Approach 2

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

  1. If the given number is negative, return false.
     
  2. If the given number is less than 10, return true.
     
  3. Create a digits variable and store the number of digits in it.
     
  4. Create a half variable to store the second half number and initialize it with zero.
     
  5. 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.
     
  6. The second half number is stored in the half variable, and the first half is stored in n.
     
  7. If the number of digits is odd, remove the last number from the first half.
     
  8. Finally, check whether the first half equals the second half. If both are equal, return true.
     
  9. 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.
DRY Run example

split = 1.

number = 144.

Second loop

  • split = 1*10 + 144%10.
  • number = 144/10.
DRY Run example

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

C++ code 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

python code 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).

Check out this problem - Reverse Nodes In K Group
Must Read  C Program to Reverse a Number

Frequently Asked Questions

What is a palindrome number?

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.


To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Tiling Problem Using Divide and Conquer Algorithm
Next article
Check if the array can be split into subarrays such that the XOR of the length of the Longest Decreasing Subsequences of those subarrays is 0
Live masterclass