Sum Of N Digit Palindromes

Easy

0/40

Average time to solve is 10m

4 upvotes

Asked in company

Problem statement

You are given an integer 'N'. Your task is to return the sum of all N-digit numbers which are palindrome. A number is said to be palindrome if the number formed by reversing its digits is the same as the given number before.

For Example :

If the value of 'N' is 1, then the answer for this is 45.

Because the list of one-digit numbers is [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 ] and each and every number is a palindrome in itself. So our ans equals (1+ 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0) = 45.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' number of test cases. 

Each of the next 'T' lines contains a single integer 'N'.

Output Format :

For each test case print only one line containing an integer representing the sum of N-digit palindromes.

Note:

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

Constraints:

1 <= 'T' <= 50
1 <= 'N' <= 12

Time Limit : 1 sec

Sample Input 1:

2
1
2

Sample Output 1:

45
495

Explanation For Sample Input 1:

For the first test case:
The list of 1-digit numbers is [ 1, 2, 4, ...., 9 ] among this list all are palindromes and their sum is 45.

For the second test case:
The list of 2-digit numbers is [ 10, 11, 12, ….., 99 ] among this list the numbers that are palindrome are [ 11, 22, 33, 44, 55, 66, 77, 88, 99 ]. Return the sum of this list i.e (11 + 22 + 33 + 44 + 55 + 66 + 77 + 88 + 99 ) = 495.

Sample Input 2:

2
3
5

Sample Output 2:

49500
49500000

Hint 1

Hint 2

We can traverse from 1 to ‘N’.

Approaches (2)

Approach 1

Approach 2

Traversing

Initialize the variable 'SUM' = 0.
As all 'N' digit numbers are in the range [10 ^ (N-1), (10^N) - 1] including endpoints.
Traverse each number in this range and check that the current number is palindrome or not. If it’s a palindrome add the current number in the variable 'SUM'.
Return the 'SUM'.

Time Complexity

O((10 ^ N) * N), where ‘N’ is the given integer.

As we have to traverse all the numbers formed using ‘N’ digits O(10 ^ N) and check for each number whether it’s a palindrome or not O(N).

Space Complexity

O(1)

Only constant extra space is required.

(100% EXP penalty)

Sum Of N Digit Palindromes

Console