Find the expected number of carries when adding two numbers, each at most N digits long.

Explanation:

let E[i] = probability that addition at i^{th} place results in carry.
Then E[1] = 45/100
and E[i] = 45/100 + 10/100 * E[i-1] for i > 1
(Justification in next section)

By linearity of expectation,

Answer[N] = E[1] + E[2] … E[N]

Therefore, one could first pre-compute all E[i]'s and then Answer[i]'s in O(N) time overall.

This gives complexity of O(N+T).

However, it is also possible to have O(1) time per testcase.
This can be done by rewriting the above equation as: (0.5 - E[i]) = 10/100 * (0.5 - E[i-1])
Therefore, (0.5 - E[i]) = (0.5 - E[1]) / 10^{i-1} = 0.00…(i times 0)…05

So, Answer[N] = E[1] + E[2] … E[N] = 0.5 * n - 0.0555…(n times 5)…5

Justifications:

Adding the digits at i^{th} place results in a carry if

The sum of those two digits is more than 9. All such pairs of digits are (1, 9), (2, 9), (3, 9) …, (2, 8), (3, 8), …, (3, 7), (4, 7), …, (9, 1). There are 45 such pairs, therefore probability of this happening is 45/100.

The sum of those two digits is exactly 9, and there was a carry from i-1^{th} position. The sum of digits is 9 for the pairs (0, 9), (1, 8), (2, 7), … (9, 0). The probability of this happening is 10 / 100 * E[i-1].

why we are considering each pair two times like when we are calculating pairs with 9 we’ve already considerd 9+8…but again when calculating pairs for 8 we included 8+9…aren’t they same ???

I used the formula E[i]=0.45*i+E[i-1]/10 and got it accepted . I don’t understand how your formula and mine can give the same results. Also your justification is quite unclear. Could you please elaborate it properly.

No, they are not same. Adding 1 and 9 is different from adding 9 and 1. This is because both numbers are chosen independently.
If you consider 1+9 same as 9+1, then you are giving more “weight” to the case when both digits are same(there will be 10/55 such cases as compared to 10/100 in the original setting).
To see this quickly, make your base 2, and consider 1 digit numbers. Carry is there only when you add 1+1. Since you consider 0+1 same as 1+0, you will give answer 1/3. whereas, it is clearly 1/4(probability that both numbers are 1).

You should have got over this doubt by seeing the answer 0.45 for single digit numbers. If you don’t include repetition then it should have been 0.30 as there would be 30 such cases. But as the sum of 1,2,3…,10 is 55; it takes less than a millisecond to observe that number of cases is 45 (1+2+3+…+9).

Adding (21 and 19) and (29 and 11) are considered to be different although in both cases the carry is due to 9+1, for the reason cum explanation mentioned by @utkarsh_lath