3
$\begingroup$

In the example, it says that its easier to count the number of integers that do not contain the digit 9

what i did is, since its from $0$ to $1{,}000{,}000$ i can simply say its to $999{,}999$ and for 6 digits there are 8 choices of numbers, so $6^8$. now subtract that from $1{,}000{,}000$ and we get $679{,}616$ as the numbers that contain the digit $9$, is that correct?

$\endgroup$
  • 2
    $\begingroup$ (1) there are ten different digits (2) choosing 6 digits independently from a set of 8 would give you $8^6$ choices. $\endgroup$ – Joffan Apr 10 '17 at 20:54
  • $\begingroup$ @Joffan why a set $8$ digits? There are $9$ digits that are not $9$, but you need to take into account whether leading zeroes are permitted. $\endgroup$ – Χpẘ Apr 10 '17 at 21:07
  • 2
    $\begingroup$ It is easier to allow leading zeros and it doesn't affect the answer. 000xxx contains a 9 if and only if xxx contains a 9. $\endgroup$ – badjohn Apr 10 '17 at 21:09
  • $\begingroup$ @user2460798 I am commenting on the question as written. You'll note I already mentioned the digit count. $\endgroup$ – Joffan Apr 10 '17 at 21:11
  • $\begingroup$ @badjohn Right. Because a blank (or absence of a zero) is the same as a zero. Would've been different if the question was about the digit 0. $\endgroup$ – Χpẘ Apr 10 '17 at 21:16
5
$\begingroup$

You have six slots. In each slot you can place any digit between 0 and 9 (ten possibilities). This generates all $10^6$ possible numbers from 0 to $999,999$ (ignoring leading zeros as necessary). To generate a number that doesn't contain a nine, there are only nine possibilities for each slot (namely, $0$ through $8$), yielding $9^6$. So the total number of integers between zero and $999,999$ that do contain the digit nine is $10^6-9^6$. This is the same as the number of positive integers between 0 and a million that do so.

$\endgroup$
2
$\begingroup$

So while the "excluding leading zeros" thing can work and all, I find that allowing them actually simplifies the problem.

You have a list of 9 digits $\{0, 1, 2, ..., 8\}$ and you want to write all possible numbers with them of 6 characters (we'll add +1 for the number 1,000,000)

you get $9$ digits in $6$ different positions, leading to $9^6$ distinct numbers (these include those with leading 0s: 000,000; 000,010; 001,305; etc). So there's no need to worry about the 'length' of a number because we can just assume those of length 5 have one starting 0s, those with 4 have 2 starting 0s, etc. Otherwise you have to account for the position of the first non-zero digit and then add the possibility of 0's elsewhere for numbers like $050,000 = 50,000$

So up to length 6 (aka 888,888 [because anything past that will contain a 9 ]) we have $9^6$ distinct numbers and we just need to add 1 more to account for the number $1,000,000$ and we end up with $9^6+1$ total numbers between 0 and 1M that do not contain the digit 9

(if you want those that do, take $1,000,001-9^6-1$)

$\endgroup$
  • $\begingroup$ The question does ask for 'positive integers', which 0 is not a part of, so you may want to handle that on your own. By definition 0 is NOT positive, but it was included in the range 0-1M provided, so it is possible they meant to exclude the endpoints on the range. $\endgroup$ – jorgeegroj Apr 10 '17 at 21:21
1
$\begingroup$

No, you forgot about $5$-digit, $4$-digit, $3$-digit, $2$-digit, $1$-digit numbers. Proceed in the same way as you have done

( As mentioned by @Joffan, it must be $8^6$ rather than $6^8$, not that too it should be 8.9^5) )

You will get :

$$999,999 - (8.9^5+8.9^4+8.9^3+8.9^2+8.9^1+8)= 999,999- \Big(8 \cdot \frac{9^6-1}{9-1}\Big) = 468,559$$

$8$ beacuse we have excluded $0$ in the first place.

$\endgroup$
0
$\begingroup$

First, using base 10, we find that there are 1,000,000 numbers between 0 and 1,000,000 that use the digits 0-9, and using base 9, converting 1,000,000 base 9 to base 10, we find that 531,441 numbers use numbers 0-8, subtracting the # of numbers that use 0-8 from the amount of numbers that use 0-9, we get that the amount of positive integers between 0 and 1,000,000 that use 9 is 468,559 numbers

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.