How to Solve Palindrome Generator

Written By

Adam Bhula

Palindrome Generator Introduction

The Palindrome Generator problem asks us to print out all 8-digit palindromes with the limitation that string manipulation isn't allowed. One important thing to remember when solving this problem is that all even-length palindromes exhibit a unique property in that they are multiples of 11. Using this we can

Palindrome Generator Problem

Print out all 8 digit palindromes. Limitation: We can't use string manipulation.

Palindrome Generator Solutions

To generate even-length palindromes with 8 digits, while avoiding string manipulation we utilize the divisibility property of palindromes by 11. By examining numbers in the range from 10,000,001 to 99,999,999, we iterate through the elements by adding 11 each time and then passing the value through to our isPalindrome function.

Divisibility by 11 is a useful criteria because all even-length palindromes, including those with leading zeros, exhibit this property. By only passing values that are multiples of 11 we can optimize our run time.

To determine if a number is a palindrome, a simple algorithm is used that involves reversing the number digit by digit and comparing it to the original number. By applying these two steps, we can generate the desired even-length palindromes with 8 digits, meeting the specified requirements.

However this is under the premise that we are not accepting 8 digit numbers with leading 0's, this would require some level of string manipulation.

def generate_even_palindromes():
    palindromes = []

for num in range(10000001, 100000000, 11):
        if is_palindrome(num):
            palindromes.append(num)

return palindromes

def is_palindrome(num):
    reversed_num = 0
    original_num = num

while num > 0:
        remainder = num % 10
        reversed_num = (reversed_num * 10) + remainder
        num //= 10

return original_num == reversed_num

# Generate even number palindromes with 8 digits and multiples of 11
even_palindromes = generate_even_palindromes()

# Print the generated palindromes
for palindrome in even_palindromes:
    print(palindrome)

Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the number of 8-digit numbers between 10,000,000 and 99,999,999 divide by 11. The algorithm iterates through this range by 11 each time and checks for palindrome property.
• Space Complexity: O(1), as the algorithm does not utilize any additional data structures that grow with the input size. It only stores the resulting palindromes in a list, which has a fixed maximum length (the number of even-length palindromes with 8 digits).