Find Palindromes

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
30 upvotes
Asked in companies
GrabQuikrIQVIA

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
 2
 12
 5
Sample Output 1:
1 2 3 4 5 6 7 8 9 11
1 2 3 4 5
Explanation:
For the first test case, all the single-digit numbers are palindromic, and the number 11 is also palindromic. Hence the output is [1, 2, 3, 4, 5, 6, 7, 8, 9, 11].

For the second test case, N is less than 9. Therefore all the numbers from 1 to N are palindromes. Hence the output is [1, 2, 3, 4, 5].
Sample Input 2:
 2
 15
 22
Sample Output 2:
1 2 3 4 5 6 7 8 9 11
1 2 3 4 5 6 7 8 9 11 22
Hint

 Try to think of a brute force approach by traversing from 1 to N to solve the problem.

Approaches (2)
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.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Find Palindromes
Full screen
Console