How many nine digit numbers are there that contain exactly two 5's

Question

I manage to do it but I don't know if it's correct and also I don't know how to prove it in c++ or any other code

Answer 1

9^7*8+9^6*8*8*7/2

Answer 2

2 digits have fixed value 5, the other 7 digits can be 0-9, but not 5 (9 possible choises for each digit, unless it's the first digit, which cannot be 0). So when the first digit is 5, we have 9^7 ways to choose other digit and 8 places to store the second 5. When the first digit is not 5, we have 8 choises for the first digit, 9^6 choises for others which are not fives and finally we can place the fives in 8*7/2 positions.

Answer 3

OK, here is my stab at it. You can do this in code by "brute-force" i.e. simply increment a counter and count the numbers of 5's in each number (convert number to string and count 5s, make sure you skip ones with > 2 x 5s, etc). But that would be overkill - why not just use a bit of logic?

- With one 5 in the leftmost position the other 5 can be in one of 8 remaining positions to its right. Lets show this as:
55xxxxxxx
5x5xxxxxx
5xx5xxxxx
5xxx5xxxx
...
5xxxxxxx5
So here we have 8 possible "equations", but where every 'x' can be one of 9 possible values (not 10, since 5 cannot repeat again).
Since the order is not important in the x's, we have a combination of 7 digits (x's), each with 9 possible values.
This is 8 * 9^7.

- Repeat but move the leftmost 5 one position right, now the other 5 can be in one of the 7 remaining positions to its right, like this:
x55xxxxxx
x5x5xxxxx
x5xx5xxxx
x5xxx5xxx
...
x5xxxxxx5
By exactly the same argument we now have 7 * 9^7.

- And repeat the pattern, and you get:
(8 * 9^7) + (7 * 9^7) + (6 * 9^7) + (5 * 9^7) + (4 * 9^7) + (3 * 9^7) + (2 * 9^7) + (1 * 9^7)
= (8+7+6+5+4+3+2+1) * 9^7
= 36*9^7
= 172186884

NOTE: This uses 9 digits, irrespective if the most significant digits are 0, so this is also counting numbers such 000000055.