### NOTE

This editorial is aimed at people new to competitive programming , making it quite verbose.

### PROBLEM LINK:

**Author:** Pulkit Sharma

**Tester:** Satyam Gupta

**Editorialists:** Pulkit Sharma , Satyam Gupta

### DIFFICULTY:

EASY

### PREREQUISITES:

Math

### PROBLEM:

consider an N digit number A (not having any leading zeroes) . We have to find the number of possible A s such that , A + Rev(A) = 10^N - 1 , where Rev(A) is the number

formed by reversing the order of digits of A.

### EXPLANATION:

Lets represent A as d_1d_2d_3d_4...d_n

So, for N = 3 and A = 312

d_1 = 3

d_2 = 1

d_3 = 2

Now B = Rev(A) = d_nd_{n-1}...d_3d_2d_1

In our case , the target is 10^N-1 , therefore all elements of the target will be 9

So, what we need to do

(d_1 d_2 d_3d_4...d_n) + (d_n d_{n-1}...d_3d_2d_1) = 99...

We can have two cases

**Case 1 : N is odd**

Consider N = 3

A = d_1d_2d_3

Therefore,

B = d_3d_2d_1

We need to satisfy the following equations :

d1+d3 =9 , d2+d2 = 9 , d3+d1 =9

The first and the last equations are identical, So we can discard any one of them.

After discarding we are only left with 2 equations

d1+d3 =9 , d2+d2 = 9

Consider the second equation , ( d2+d2=9)

2*d2 = 9

d2 = 9/2

d2 = 4.5

But , since d2 is a digit of a number, it can never be a floating value.

*Therefore , whenever N is odd , we cannot have any solution as the middle element comes out to be 4.5 to satisfy the problemâ€™s requirements,but that is not possible.*

**Case 2 : N is even**

Consider N = 4

A = d_1d_2d_3d_4

Therefore,

B = d_4d_3d_2d_1

We need to satisfy the following equations:

d1+d4=9,d2+d3 = 9,d3+d2 = 9, d4+d1 = 9

As before, 2 equations are identical.

After eliminating them , we have

d1+d4 = 9 , d2+d3 = 9

Consider d1+d4=9

It can be easily seen , that the above equation has 10 solutions.

Namely,(0,9), (1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (9,0)

But according to the question d1 cannot be zero. Therfore there are 9 solutions in total

Now,lets see the next equation (d2+d3=9)

Similar as above , this equation has 10 solutions and all of them are valid.

As the two equations are independent of each other, Therefore we have a total of 90 solutions in total for the case where N=4

### DERIVING THE FINAL FORMULA

Now we are quite close to the solution. Whenever N is odd, the answer will be 0

And Whenever N is even we will have , 9 solutions for the first equation(made of first digits of A and B)

and 10 solutions for each of the remaining equations.

The number of remaining equations = (N/2 - 1) (As half of them are same, and we already considered the equation made of the first digits)

**Final formula = 9*10^{N/2-1}**

But there is a minor twist .

As N can go up to 10^5 therefore the resultant number from the formula will be very large.Therefore, instead of storing the number somewhere , we have to just print the result, digit by digit.

**So print 9 and N/2-1 number of zeroes.**

### AUTHORâ€™S SOLUTION:

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int t,n;
cin>>t;
while(t--)
{
scanf("%ld",&n);
if(n&1 || n<2)
{
printf("0\n");
continue;
}
n=(n/2) - 1;
printf("9");
while(n--)
printf("0");
printf("\n");
}
return 0;
}
```