CODEWITHSUNDEEP
algorithmmathcombinations
user8757849
user8757849

Reputation:

How many numbers are there that include a given digit?

Let's have 3 digit number (100-999). How many such numbers with at least one digit "2" exist?

How to make algorithm for that? Or math function?

Upvotes: 0

Views: 863

Answers (3)

Daulet Smagulov
Daulet Smagulov

Reputation: 56

Consider the probability that we do not face the specified digit in given set [0, 10^n]. It’s obvious that we can derive it as 0.9^n, then the opposite probability is

P = 1 - 0.9^n
  • for n = 1: P = 0.1;
  • for n = 2: P = 0.19;
  • for n = 3: P = 0.271.

The following formula can help to define, how many numbers in this set contain some given digit:

N = P * 10^n,

where n = 3 in your case. Also in your case we should substract the number of such values in set [0, 100]. This gives us

N = N(3) - N(2) = 271 - 19 = 252.

No loops, no recursion, pure math.

Upvotes: 1

DAle
DAle

Reputation: 9117

Inclusion-exclusion principle

How many 3-digit numbers have 2 as the first digit (2xx)? That's right - 100. And as the second digit (x2x)? 100! And as the third (xx2) - the same number. Ok, now we have 300 numbers, but we forgot about numbers in the form 22x, we count them twice. Now we need to subtract the amount of 22x, 2x2 and x22 numbers. Now we have 270 of them, but we forgot about number 222, we added it three times, and subtracted three times, we need to add it again: 271. This explanation is an example of inclusion-exclusion principle.

But that's not the end, we need to subtract all 0xx numbers having 2 as a digit. Similar approach: 271 - 10 - 10 + 1 = 252.

Dynamic programming

Ok, if you don't like the previous method, there is another one. Let's count the function F(i, has2), where i - is the digit length of the number, has2 boolean value that is equal to true if digits contain 2, otherwise it equals to false. The recurrence relation is the following:

 F(1, false) = 8, F(1, true) = 1
 F(i, true) = F(i-1, true) * 10 + F(i-1, false) 
 F(i, false) = F(i-1, false) * 9

The answer is F(3, true). 

 F(2, true) = 10 + 8 = 18
 F(2, false) = 8 * 9 = 72
 F(3, true) = 18 * 10 + 72 = 252

Upvotes: 7

Patrick Artner
Patrick Artner

Reputation: 51643

A quick'n'dirty with python is:

n  = [x for x in range(100,999) if '2' in str(x)] 

print("There are " + str(len(n)) + " numbers between 100 and 999 containing at least one '2'")
print(n)

Put that in https://pyfiddle.io/ to test.

Upvotes: 1

Related Questions