I have to find the nth number that contains the digit k or is divisible by k. (2 <= k <= 9)

Question

Example - if n = 15 and k = 3 Answer: 33 (3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 32, 33)

I began to follow the sequence, but could not formulate it

for multiple 3 → 3 + 3 + 3 + 4 + 3 + 3 + 4 + 3 + 3 + 4

to indicate 3 →

{

range in diff = 100 → 1 + 1 + 1 + 10 + 1 + 1 + 1 + 1 + 1 + 1 = f (n) say;

range in diff = 1000 → e (n) + F (n) + F (n) + 10 * F (n) + F (n) + F (n) + F (n) + F (n) + F ( n) + F (n) = ff (n) say

range in diff = 10000 → ff (n) + ff (n) + ff (n) + 10 * ff (n) + ff (n) + ff (n) + ff (n) + ff (n) + ff ( n) + ff (n)

the same goes on.

}

I should answer better than O (n) or in O (1), if possible. Please do not suggest methods to check every number in a for loop. Thanks.

Change - I searched everywhere, but could not find it anywhere, therefore, this is not a duplicate.

Answer 1

Here is one way to think about it that might point you in at least one direction (or, alternatively, chasing wild geese). Separate the two questions and remove the matching results:

(1) How many j-digit digits are divisible by k ? [j 9 / k] - [(j-1) 9 / k]

(2) How many numbers j-digit contains the number k ? 9 * 10^(k-1) - 8 x 9^(k-1)

Now we need to subtract the numbers j-digit , which are divided by k and include the number k . But how much is there?

Use the rules of divisibility to consider various cases. For instance:

 k = 2 If k is the rightmost digit, any combination of the previous j-1 digits would work. Otherwise, only combinations with 0,4,6 or 8 as the rightmost digit would work. k = 5 If k is the rightmost digit, any combination of the previous j-1 digits would work. Otherwise, only combinations with 0 or 5 as the rightmost digit would work. etc. 

(Appendix: I asked a combinatorial question about math.stackexchange and got some interesting answers . And here is a link to the OP question about math.stackexchange: https://math.stackexchange.com/questions/1884303/the-n-th-number- that-contains-the-digit-k-or-is-divisible-by-k-2-le-kl )

Answer 2

Following the גלעד ברקן answer , if you have an O (1) way of calculating d(j, k) = numbers with at least one digit k to j, dropping the numbers divisible by k, then you can calculate e(j, k) = numbers with at least k or divisible by k under j as j/k + d(j, k) .

This allows you to find f(n, k) with binary search, since k <= f(n, k) <= k*n and e(j, k) = n <=> f(n, k) = j : you are essentially trying to guess which j will give the expected n , in O (log n) it is trying.

I agree with the observation of גלעד ברקן regarding the rules of divisibility for the efficient calculation of d(j, k) ; but they are not trivial to implement, with the exception of k=5 and k=2 .

I strongly doubt that you can improve O (log n) for this problem; and it may not even be achievable for some values ​​of k .

Answer 3

This is more complicated than I thought, but I think I found a solution for the simplest case (k = 2).

At first I tried to simplify by asking the following question: what position in the sequence has numbers 10^i * k where i = 1, 2, 3, ... ? For k = 2, the numbers 20, 200, 2000, ...

 ikn 1 2 20/2 = 10 2 2 200/2 + 2* 5 = 110 3 2 2000/2 + 2* 50 + 18* 5 = 1190 4 2 20000/2 + 2*500 + 18*50 + 162*5 = 12710 i 2 10^i + 2*10^(i-1)/2 + 18*10^(i-2)/2 + 162*10^(i-3)/2 + ?*10^(i-4)/2 + ... 

In the last line, I tried to express the pattern. The first part is a number divisible by 2. Then there are i-1 extra parts for odd numbers with 2 in the first position, second and so on. The hard part is to calculate the factors (2, 18, 162, ...).

Here is a function that returns a new factor for any i:

 f(i) = 2 * 10^(i-2) - sum(10^(ix-1)*f(x), x from 2 to i-1) = 2 * 9^(i-2) [thx @m69] f(2) = 2 f(3) = 2*10 - (1*2) = 18 f(4) = 2*100 - (10*2 + 1*18) = 162 f(5) = 2*1000 - (100*2 + 10*18 + 1*162) = 1458 

Thus, using this information, we can find the following algorithm:

Find the maximum number 10^i*2 that does not exceed the position. (If n is in the range [positionOf(10^i*2), positionOf(10^i*2) + (10^i)] , then we already know the solution: 10^i*2 + (n - positionOf(10^i*2)) . For example, if we find that I = 2, we know that the following 100 values ​​are in the sequence: [201, 300], therefore, if 110 <= n <= 210, then the solution is 200 + (n-110) = n + 90.)

 int nn = positionOf(10^i * 2); int s = 10^i * 2; for (int ii = i; ii >= 0; ii--) { for (int j = 1; j < 10; j++) { if (j == 1 || j == 6) { if (n <= nn + 10^ii) return s + nn - n; nn += 10^ii; s += 10^ii; int tmp = positionOf(10^ii); if (nn + tmp > n) break; nn += tmp; s += 10^ii; } else { int tmp = positionOf(10^ii * 2); if (nn + tmp > n) break; nn += tmp; s += 10^ii * 2; } } } return s; 

This is only an unverified pseudocode (I know that you cannot use ^ in Java), ii = 1 or 0 should be considered as a special case, it is absent and how to find i isn is either shown or the answer will be too long.

Answer 4

this can be solved using binary search + dp ..... with time complexity o (logn *) for the solution see enter code here : enter code here https://ideone.com/poxhzd