I exist sometimes

Computer Science Level 2

Given a list of integers $1\cdots n$ , return the count of the number that have the number $k$ in them. For $n\leq10^{9}$ how many numbers have the number $7$ in them.

Details and Assumptions

For $n\leq10$ , the number of occurrence of $7$ is one.

For $n\leq100$ the number of occurrence of $7$ is $19$ ... $7,17,27,37,47,57,67,70,71\cdots ,79,87,97$

The answer is 612579511.

5 solutions

Benjamin Eriksson
Aug 6, 2015

For $n \leq 100$ we had 19 occurrences. Now for $n \leq 1000$ we will repeat these 19 occurences 9 times, actually 10 times but we don't want to double count them for 7xx. There are 100 numbers of the form 7xx. In total we get 9*19 + 100 = 271.

$a(n) = 9*a(n-1) + 10^{n-1}$

Or in a non-recursive form:

$a(n) = 10^n - 9^n$

Do you see a more direct way to explain why the answer is $10^n - 9^n$ ?

Hint: Complement

Calvin Lin Staff - 5 years, 8 months ago

There are also two other ways to see this result. They are both combinatorial approaches:

Numbers upto $10^n$ can be seen as numbers of the form $\overline{a_1a_2\ldots a_n}$ where $0\leq a_i\leq 9~\forall~1\leq i\leq n$

Approach 1: We fix $r$ of the $a_i$ 's as $7$ which can be done in $\binom nr$ ways and the $(n-r)$ $a_i$ 's can be any digit other than $7$ , so there are 9 choices for each of those digits. So, the number of such numbers is $\sum\limits_{r=1}^n\binom nr 9^{n-r}=-9^n+\sum\limits_{r=0}^n\binom nr 9^{n-r}=-9^n+10^n=10^n-9^n$ where the sum was simplified using the binomial theorem.

Approach 2: We consider the complement of the required event. Numbers that don't have $7$ in them have a digit other than $7$ in all the $a_i$ 's, so there are 9 choices for each $a_i$ and hence there are $9^n$ numbers upto $10^n$ which don't have $7$ in them. There are a total of $10^n$ positive integers upto $10^n$ , so we subtract $9^n$ from $10^n$ to get the number of numbers that don't have $7$ in them, so the required number of numbers is $10^n-9^n$ .

Prasun Biswas - 4 years, 10 months ago

Samarpit Swain
Aug 29, 2015

//C++
#include <iostream>
using namespace std;

int main() {
    unsigned long long int x,number,dig,count=0;
     for(x=1;x<1000000000;x++)
{     number=x;
      while(number>0)
  { 
     dig=number%10;

      if(dig==7)
      { count++;
          break;
            }
     number/=10;
  }
 }
 cout<<"The count is:"<<count;
      return 0;
}

Output:

1	`The count is:612579511`

Aditya Vipin Thomas
Sep 17, 2015

We certainly know that 10^9 doesn't contain a 7 in it. All the numbers preceding it can be represented using 9 digits. For e.g. 9 can be represented as 000000009 . So the total numbers you would be able to create would be 10^9. We know have to subtract the numbers which don't contain 7 from this value. Therefore our answer should be 10^9 -9^9=612579511

Chew-Seong Cheong
Aug 31, 2015

Let $f(k)$ be the number of integers with the digit $7$ of $1 \le n \le 10^k$ , then we have $f(k+1) = 9f(k) + 10^k$ . For $k = 9$ , it is easily calculated with an Excel spreadsheet as follows:

The answer is $\boxed{612579511}$

Andrey Bessonov
Aug 31, 2015

We have a 9 digits in the number, x1 10^9+x2 10^8+...+x9*10^0

Lets say, that c is position of last 7 (x[c] = 7) in this number, so we can insert any digit before it, and can`t insert 7 after. Number of variants will be 10^(c-1)*9^(9-c).

Answer for task is the sum of variants for all c (positions of last 7).

sum( 9^(9-c) * 10^(c-1), c = 1...9 )

I exist sometimes

The answer is 612579511.

5 solutions

0 pending reports