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

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.

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

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.

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

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.

• Reverse a String using Stack
• How To Sort A Stack Using Recursion?
• Difference between Array, Queue & Stack
• Expression Evaluation Using Stack

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!