Skip to content

Palindrome Numbers

Problem Statement

Given an integer x, return true if x is a palindrome number. Palindrome numbers are those that read the same forwards and backwards. For example, 121 is a palindrome, while 123 is not.

Constraints

  • -2^31 <= x <= 2^31 - 1

Approach 1: Without Using String

  • Reverse the entire integer and compare it with the original
  • Time Complexity: O(log(n)), where n is the number of digits in the input number.
  • Space Complexity: O(1).
  • This approach is also efficient, but it involves reversing the entire number.

Flowchart

graph LR;
    Start[Start] --> CheckNegativeNum{num >= 0}
    CheckNegativeNum -- Yes --> Initialize[Initialize variables]
    CheckNegativeNum -- No --> ReturnFalse[Return False]
    Initialize --> Loop[Start Loop]
    Loop --> |"num > 0"| ExtractDigit[Extract rightmost digit of num]
    Loop --> |"num == 0"| EndLoop[End Loop]
    ExtractDigit --> CalculateReverse[Calculate reverse]
    CalculateReverse --> UpdateReverse[Update reverse]
    CalculateReverse --> UpdateNum[Update num]
    UpdateReverse --> Loop
    UpdateNum --> Loop
    EndLoop --> |"reverse == original"| ReturnTrue[Return True]
    EndLoop --> |"reverse != original"| ReturnFalse
    ReturnTrue --> End[End]
    ReturnFalse --> End

    classDef startEnd fill:#9f9,stroke:#333,stroke-width:2px;
    class Start,End startEnd;

Pseudocode

function isPalindrome(x):
    if x < 0:
        return False
    original = x
    reversed_x = 0
    while x > 0:
        # Extract the last digit of x
        last_digit = x % 10
        # Append the last digit to the reversed number
        reversed_x = reversed_x * 10 + last_digit
        # Remove the last digit from x
        x = x // 10
    return original == reversed_x

Explanation

Example 1: num = 121

  • The number num is not negative, so the condition if num < 0: is not met.
  • We initialize reverse to 0 and original to 121 (the original value of num).
  • The while loop starts since num > 0.
  • In the first iteration:
  • digit is 121 % 10 = 1.
    • reverse becomes 0 * 10 + 1 = 1.
    • num becomes 121 // 10 = 12.
  • In the second iteration:
    • digit is 12 % 10 = 2.
    • reverse becomes 1 * 10 + 2 = 12.
    • num becomes 12 // 10 = 1.
  • In the third iteration:
    • digit is 1 % 10 = 1.
    • reverse becomes 12 * 10 + 1 = 121.
    • num becomes 1 // 10 = 0.
  • The loop ends since num is no longer greater than 0.
  • Finally, the function returns reverse == original, which is 121 == 121, so it returns True.

Example 2: num = -121

  • Since num is negative, the function immediately returns False.

Example 3: num = 10

  • num is not negative.
  • In the first iteration of the loop, num becomes 1 after removing the last digit.
  • The loop ends, and the function returns reverse == original, which is 1 == 10, so it returns False.

Solution Code Block

Without Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def is_palindrome(x: int) -> bool:
    if x < 0:
        return False
    if x == 0:
        return True
    if x % 10 == 0:
        return False
    num_reversed = 0
    original_x = x
    while original_x > 0:
        last_digit = original_x % 10
        num_reversed = num_reversed * 10 + last_digit
        original_x //= 10
    return x == num_reversed

print(is_palindrome(121))  # True
print(is_palindrome(-121))  # False
print(is_palindrome(10))  # False
Without Using Strings
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

bool isPalindrome(int x) {
    if (x < 0) {
        return false;
    }
    if (x == 0) {
        return true;
    }
    if (x % 10 == 0) {
        return false;
    }
    int numReversed = 0;
    int originalX = x;
    while (originalX > 0) {
        int lastDigit = originalX % 10;
        numReversed = numReversed * 10 + lastDigit;
        originalX /= 10;
    }
    return x == numReversed;
}

int main() {
    std::cout << std::boolalpha;
    std::cout << isPalindrome(121) << std::endl;  // true
    std::cout << isPalindrome(-121) << std::endl; // false
    std::cout << isPalindrome(10) << std::endl;   // false
    return 0;
}
Without Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
fn is_palindrome(x: i32) -> bool {
    if x < 0 {
        return false;
    }
    if x == 0 {
        return true;
    }
    if x % 10 == 0 {
        return false;
    }
    let mut num_reversed = 0;
    let mut original_x = x;
    while original_x > 0 {
        let last_digit = original_x % 10;
        num_reversed = num_reversed * 10 + last_digit;
        original_x /= 10;
    }
    x == num_reversed
}

fn main() {
    println!("{}", is_palindrome(121)); // true
    println!("{}", is_palindrome(-121)); // false
    println!("{}", is_palindrome(10)); // false
}
Without Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import "fmt"

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    if x == 0 {
        return true
    }
    if x%10 == 0 {
        return false
    }
    numReversed := 0
    originalX := x
    for originalX > 0 {
        lastDigit := originalX % 10
        numReversed = numReversed*10 + lastDigit
        originalX /= 10
    }
    return x == numReversed
}

func main() {
    fmt.Println(isPalindrome(121))  // true
    fmt.Println(isPalindrome(-121)) // false
    fmt.Println(isPalindrome(10))   // false
}
Without Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Palindrome {
    public static boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        if (x % 10 == 0) {
            return false;
        }
        int numReversed = 0;
        int originalX = x;
        while (originalX > 0) {
            int lastDigit = originalX % 10;
            numReversed = numReversed * 10 + lastDigit;
            originalX /= 10;
        }
        return x == numReversed;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));  // true
        System.out.println(isPalindrome(-121)); // false
        System.out.println(isPalindrome(10));   // false
    }
}
Without Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isPalindrome(x) {
    if (x < 0) {
        return false;
    }
    if (x === 0) {
        return true;
    }
    if (x % 10 === 0) {
        return false;
    }
    let numReversed = 0;
    let originalX = x;
    while (originalX > 0) {
        const lastDigit = originalX % 10;
        numReversed = numReversed * 10 + lastDigit;
        originalX = Math.floor(originalX / 10);
    }
    return x === numReversed;
}

console.log(isPalindrome(121));  // true
console.log(isPalindrome(-121)); // false
console.log(isPalindrome(10));   // false

TryIt

Approach 2: Using String

  • Convert the integer to a string and then compare the string with its reverse.
  • Time Complexity: O(n), where n is the number of digits in the input number.
  • Space Complexity: O(n), where n is the number of digits in the input number.
  • While this approach is straightforward, it requires additional space to store the string representation of the number.

Flowchart

graph LR;
    Start[Start] --> ConvertToStr[Convert integer to string]
    ConvertToStr --> ReverseString[Reverse the string]
    ReverseString --> CompareStrings[Compare original and reversed strings]
    CompareStrings --> |"strings are equal"| ReturnTrue[Return True]
    CompareStrings --> |"strings are not equal"| ReturnFalse[Return False]
    ReturnTrue --> End[End]
    ReturnFalse --> End

    classDef startEnd fill:#9f9,stroke:#333,stroke-width:2px;
    class Start,End startEnd;

Pseudocode

function isPalindrome(num):
    // Convert the integer to a string
    str_num = str(num)
    // Reverse the string
    reversed_str = str_num[::-1]
    // Check if the original string is equal to the reversed string
    if str_num == reversed_str:
        return True
    else:
        return False

Explanation

Example 1: num = 121

  • We convert the integer 121 to the string "121".
  • Reversing the string "121" gives us "121".
  • Since the original string is equal to the reversed string, the function returns True.

Example 2: num = -121

  • Converting a negative number to a string includes the negative sign, so "-121" is the string representation.
  • Reversing the string "-121" gives us "121-", which is not equal to the original string.
  • Therefore, the function returns False.

Example 3: num = 10

  • Converting the integer 10 to a string gives us "10".
  • Reversing the string "10" gives us "01", which is not equal to the original string.
  • Thus, the function returns False.

Solution Code Block

With Using String
1
2
3
4
5
6
7
def is_palindrome(x: int) -> bool:
    str_x = str(x)
    return str_x == str_x[::-1]

print(is_palindrome(121))  # True
print(is_palindrome(-121)) # False
print(is_palindrome(10))   # False
With Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>

bool isPalindrome(int x) {
    std::string strX = std::to_string(x);
    for (size_t i = 0; i < strX.length() / 2; i++) {
        if (strX[i] != strX[strX.length() - i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    std::cout << std::boolalpha;
    std::cout << isPalindrome(121) << std::endl;  // true
    std::cout << isPalindrome(-121) << std::endl; // false
    std::cout << isPalindrome(10) << std::endl;   // false
    return 0;
}
With Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
fn is_palindrome(x: i32) -> bool {
    let str_x = x.to_string();
    str_x == str_x.chars().rev().collect::<String>()
}

fn main() {
    println!("{}", is_palindrome(121)); // true
    println!("{}", is_palindrome(-121)); // false
    println!("{}", is_palindrome(10)); // false
}
With Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import (
    "fmt"
    "strconv"
)

func isPalindrome(x int) bool {
    strX := strconv.Itoa(x)
    for i := 0; i < len(strX)/2; i++ {
        if strX[i] != strX[len(strX)-i-1] {
            return false
        }
    }
    return true
}

func main() {
    fmt.Println(isPalindrome(121))  // true
    fmt.Println(isPalindrome(-121)) // false
    fmt.Println(isPalindrome(10))   // false
}
With Using String
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Palindrome {
    public static boolean isPalindrome(int x) {
        String strX = Integer.toString(x);
        int n = strX.length();
        for (int i = 0; i < n / 2; i++) {
            if (strX.charAt(i) != strX.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));  // true
        System.out.println(isPalindrome(-121)); // false
        System.out.println(isPalindrome(10));   // false
    }
}
With Using String
1
2
3
4
5
6
7
8
function isPalindrome(x) {
    const strX = x.toString();
    return strX === strX.split('').reverse().join('');
}

console.log(isPalindrome(121));  // true
console.log(isPalindrome(-121)); // false
console.log(isPalindrome(10));   // false

TryIt