In the last line : E[i] = 45/100 + 9 * E[i-1] / 100 ?? I think it should be E[i] = 45/100 + 10 * E[i-1] / 100
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
You got it right, it gives WA due to precision issues.
But you seem to not to know where precision is coming into picture.
It is coming when you print your result !
cout prints upto 6 significant digits.
This fact often gives wrong answer and people remain clueless about their error.
@bb_1: How do u get this E[i]=0.45*i+E[i-1]/10 recurrence relation?
plz explain ur approach bcz I didn’t understand from editorial.
The probability that we get a carry from i-1 th place is E[i-1]. Since the digits at ith place are independent of the digits at i-1 th place, we have
Prob[there was a carry from i-1 th place and sum of digits at i th place is 9] = Prob[there was a carry from i-1 th place] * Prob[sum of digits at i th place is 9] = E[i-1] * 10/100.
1 Like
just use:
cout<<fixed <<arr[n]<<endl;
and it will get AC 
have we include the case when the first digit for a number(N>1) is 0…we keep on counting if the sum is 9 without testing that the first number cant be 0…