Find Palindromes
You are given an integer ‘N’. Your task is to find all palindromic numbers from 1 to ‘N’.

Palindromic integers are those integers that read the same backward or forwards.

Note:

Order of numbers should be in the non-decreasing matter.

For example:

You are given ‘N’ as 12, so the output should be [1, 2, 3, 4, 5, 6, 7, 8, 9, 11], as all single-digit numbers are palindromic, and 11 is also a palindromic number.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case consists of a single integer ‘N’, representing the given integer.

Output Format:

For each test case, print all the palindromic integers space-separated from 1 to ‘N’ in increasing order. Print a separate line for each test case.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find Palindromes

You are given an integer ‘N’. Your task is to find all palindromic numbers from 1 to ‘N’.

Palindromic integers are those integers that read the same backward or forwards.

Note:

Order of numbers should be in the non-decreasing matter.

For example:

You are given ‘N’ as 12, so the output should be [1, 2, 3, 4, 5, 6, 7, 8, 9, 11], as all single-digit numbers are palindromic, and 11 is also a palindromic number.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case consists of a single integer ‘N’, representing the given integer.

Output Format:

For each test case, print all the palindromic integers space-separated from 1 to ‘N’ in increasing order.

Print a separate line for each test case.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^9

Time Limit: 1 sec

Accepted Answer

Brute Force

In this approach, iterate through the integers 1 to N, then check for each integer if it is a palindrome or not.

To check if an integer is a palindrome, convert the integer into a string and check if it is equal to the reverse.

We define a function isPalindrome(num), where we check if num is palindrome or not and return the result accordingly.

Algorithm:

The function isPalindrome(num).
- Convert the number num into a string and store it in strNum.
- Check if strNum is equal to its reverse, then return true. Otherwise, return false.
Create an empty array numList.
Iterate num through the numbers, from 1 to N,
- For each num call isPalindrome(num) function, if the function returns true, insert num in numList.
Finally, return the array numList.

Space Complexity: OtherExplanation:

O(M), where M is the number of palindromes between 1 to N.

We store the number as a string for each number from 1 to N, and it will take O(1) space. We are storing all the palindromes in an array that takes O(M) space. Hence the overall space complexity becomes O(M).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)), where N is the given integer.

We are iterating through all the numbers from 1 to N, and for each number, we need to check if it is a palindrome that takes O(log(N)) time because the number of digits in a number is log(N). So the overall time complexity becomes O(N*log(N)).

Java (SE 1.8)

/*
    Time Complexity: O(N*log(N))
    Space Complexity: O(M)

    Where N is the integer given and M is the number of palindromes.
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
	public static boolean isPalindrome(int num) {
		
		// Convert the number into the string
		String strNum = Integer.toString(num);

		String rev = new StringBuilder(strNum).reverse().toString();

		// Check if the string is equal to its reverse
		return strNum.equals(rev);
	}

	public static int[] getPalindromes(int n) {

		// Create an empty arrayList for palindromes
		List numList = new ArrayList<>();

		// Iterating through 1 to N
		for (int num = 1; num < n + 1; ++num) {

			// Check if number num is a palindrome
			if (isPalindrome(num)) {
				numList.add(num);
			}
		}
		int ans[] = numList.stream().mapToInt(i -> i).toArray();

		// Return the array
		return ans;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log(N))

    Space Complexity: O(M)



    Where N is the integer given and M is the number of palindromes.

*/



bool isPalindrome(int num)

{

    // Convert the number into the string

    string strNum = to_string(num);



    string rev = string(strNum.rbegin(), strNum.rend());



    // Check if the string is equal to its reverse

    return strNum == rev;

}



vector getPalindromes(int n)

{

    // Creating an empty array

    vector numList;



    // Iterating through 1 to N

    for(int num = 1; num < n + 1; ++num)

    {

        // Check if number num is a palindrome

        if(isPalindrome(num))

        {

            numList.push_back(num);

        }

    }



    // Return the array

    return numList;

}

Python (3.5)

'''
    Time Complexity: O(N*log(N))
    Space Complexity: O(M)

    Where N is the integer given and M is the number of palindromes.
'''

def isPalindrome(num):

    # Convert the number into the string
    strNum = str(num)

    # Check if the string is equal to its reverse
    return strNum == strNum[::-1]


def getPalindromes(n):

    # Creating an empty array
    numList = []

    # Iterating through 1 to N
    for num in range(1, n + 1):

        # Check if number num is a palindrome
        if(isPalindrome(num)):
            numList.append(num)

    # Return the array
    return numList

Accepted Answer

Optimised Approach

In this approach, we try to create all the palindrome integers till N. To create the palindromes of odd length, we remove the last digit from the number and add the remaining digits in reverse order to the previous digits. To generate the palindrome of even length, we add the reverse of the current number to its digits.

We define a function createPalindrome(num, makeOdd), which returns even length or odd length palindrome created from num.

Algorithm:

Function createPalindrome(num, makeOdd)
- Set the variables n and palindrome as num
- If makeOdd is equal to 1, set n equal to n /10.
- While n is greater than 0
  - Set palindrome equal to palindrome * 10 + (n % 10)
  - Set n equal to n /10.
- Finally, return palindrome.
Create an empty array numList.
Iterate makeOdd from 0 to 1.
- Set the variable num equal 1.
- Set palindrome equal to createPalindrome(num, makeOdd)
- While palindrome is not greater than n
  - Insert palindrome in numList
  - Increase num by 1.
  - Set palindrome equal to createPalindrome(num, makeOdd)
Sort the array numList.
Finally, return the array numList

Space Complexity: OtherExplanation:

O(M), where M is the number of palindromes between 1 to N.

We are storing all the palindromes in an array that takes O(M) space. Hence the overall space complexity becomes O(M).

Time Complexity: OtherExplanation:

O(M* (log(M))), where M is the number of palindromes between 1 to N.

The time complexity O(M*log(N)) is used to make the array of M palindromes, and sorting the array of palindromes takes O(M*log(M)), So the overall time complexity becomes O(M* log(M) + M* log(N)) = O(M* (log(M))).

Java (SE 1.8)

/*
    Time Complexity: O(M* Log(M))
    Space Complexit: O(M)

    Where M is the number of palindromes present between 1 and N
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.IntFunction;

public class Solution {
	private static int createPalindrome(int num, int makeOdd) {

		// Store number to be reversed
		int n = num;
		int palindrome = num;

		// Check if the palidrome to be created is odd
		if (makeOdd > 0) {

			// Remove the last digit if odd palindrome is to be created
			n = n / 10;
		}

		// Reverse the number and add it in palindrome
		while (n > 0) {
			palindrome = palindrome * 10 + (n % 10);
			n = n / 10;
		}

		// Return the palindrome
		return palindrome;
	}

	public static int[] getPalindromes(int n) {
		
		// Create an empty arrayList for palindromes
		List numList = new ArrayList<>();

		// Run the loop for even and odd length palindromes
		for (int makeOdd = 0; makeOdd < 2; ++makeOdd) {
			int num = 1;
			int palindrome = createPalindrome(num, makeOdd % 2);

			// Loop until palindrome is not greater than n
			while (palindrome <= n) {
				numList.add(palindrome);
				num += 1;

				// Create the next palindrome
				palindrome = createPalindrome(num, makeOdd % 2);
			}
		}

		// Sort the arrayList before returning
		Collections.sort(numList);
		int ans[] = numList.stream().mapToInt(i -> i).toArray();
		return ans;
	}

}

Python (3.5)

'''

    Time Complexity: O(M* Log(M))

    Space Complexit: O(M)



    Where M is the number of palindromes present between 1 and N

'''



def createPalindrome(num, makeOdd):



    # Store number to be reversed

    n = num

    palindrome = num



    # Check if the palidrome to be created is odd length

    if(makeOdd == 1):



        # Remove the last digit if odd length palindrome is to be created

        n = n // 10



    # Reverse the number and add it in palindrome

    while(n > 0):

        palindrome = palindrome * 10 + (n % 10)

        n = n // 10



    # Return the palindrome

    return palindrome





def getPalindromes(n):



    # Create a empty list for palindromes

    numList = []



    # Run the loop for even and odd length palindromes

    for makeOdd in range(2):



        num = 1

        palindrome = createPalindrome(num, makeOdd)



        # Loop until palindrome is not greater than n

        while (palindrome <= n):



            numList.append(palindrome)

            num += 1



            # Create the next palindrome

            palindrome = createPalindrome(num, makeOdd)



    # Sort the list before returning

    numList.sort()

    return numList

C++ (g++ 5.4)

/*

    Time Complexity: O(M* Log(M))

    Space Complexit: O(M)



    Where M is the number of palindromes present between 1 and N

*/



#include 



int createPalindrome(int num, int makeOdd)

{

    // Store number to be reversed

    int n = num;

    int palindrome = num;



    // Check if the palidrome to be created is odd length

    if(makeOdd == 1)

    {

        // Remove the last digit if odd length palindrome is to be created

        n = n / 10;

    }



    // Reverse the number and add it in palindrome

    while(n > 0)

    {

        palindrome = palindrome * 10 + (n % 10);

        n = n / 10;

    }



    // Return the palindrome

    return palindrome;

}



vector getPalindromes(int n)

{

    // Create an empty array for palindromes

    vector numList;



    // Run the loop for even and odd length palindromes

    for(int makeOdd = 0; makeOdd < 2; ++makeOdd)

    {

        int num = 1;

        int palindrome = createPalindrome(num, makeOdd);



        // Loop until palindrome is not greater than n

        while (palindrome <= n)

        {

            numList.push_back(palindrome);

            num += 1;



            // Create the next palindrome

            palindrome = createPalindrome(num, makeOdd);

        }

    }



    // Sort the array before returning

    sort(numList.begin(), numList.end());

    return numList;   

}

You are given an integer ‘N’. Your task is to find all palindromic numbers from 1 to ‘N’.

Palindromic integers are those integers that read the same backward or forwards.

Note:

For example:

Input Format :

Output Format:

Note:

Constraints:

Top IQVIA SDE-2 interview questions & answers

Popular interview questions of SDE-2