Last Updated: 11 Dec, 2020
Find Palindromes
Moderate
Asked in companies
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
Approaches
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.
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