Sum Of N Digit Palindromes
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.

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

Question

Sum Of N Digit Palindromes

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.

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

Accepted Answer

Run a loop from 10^(n-1) to 10^(n) – 1 and check when the current number is palindrome or not. If it is, adds its value to answer.

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

Only constant extra space is required.

Time Complexity: O(1)Explanation:

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

Accepted Answer

Sum Of All N digit Palindromic Numbers

If we observe carefully the sum of ‘N’ digit palindromes is forming a series i.e 45, 495, 49500, 495000, 49500000 i.e for ‘N’ = 1 => 'SUM' = 45, for N = 2 => 'SUM' = 495
Thus we can find this using a mathematical formula as 'SUM' = (99 / 2) * (10^(N -1)) * (10 ^ ((N-1)/2)).
Update the variable 'SUM' by value after the above calculation and return it.

Space Complexity: O(1)Explanation:

O(1)

Only constant extra space is required.

Time Complexity: O(logn)Explanation:

O(LogN), where ‘N’ is the number of digits in the palindromic number.

As we are calculating powers of 10, it will take logarithmic time using binary exponentiation. hence the overall complexity will be O(LogN).