Ich muss die n-te Nummer finden, die die Ziffer k enthält oder durch k teilbar ist. (2 <= k <= 9)

Question

Beispiel - wenn n = 15 & k = 3 Antwort: 33 (3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31 , 32, 33)

begann ich die Sequenz folgende konnte aber nicht

für ein Vielfaches von 3 formulieren -> 3 + 3 + 3 + 4 + 3 + 3 + 4 + 3 + 3 + 4

zum Beinhalten digit 3 ->

{

Bereich in diff = 100 -> 1 + 1 + 1 + 10 + 1 + 1 + 1 + 1 + 1 + 1 = f (n) sagen ;

Bereich in diff = 1000 -> f (n) + f (n) + f (n) + 10 * f (n) + f (n) + f (n) + f (n) + f (n) + f (n) + f (n) = ff (n) sagen

Bereich in diff = 10000 -> ff (n) + ff (n) + ff (n) + 10 * ff (n) + ff (n) + ff (n) + ff (n) + ff (n) + ff (n) + ff (n)

dasselbe geht weiter.

}

Ich habe in besser als O (n) oder in O (1), wenn möglich zu beantworten, bitte nicht vorschlagen Methoden wie jede Zahl in einem for-Schleife zu überprüfen. Vielen Dank.

Edit-Ich habe überall gesucht, konnte aber nirgendwo gefunden so gefunden, es ist kein Duplikat.

Answer 1

Hier ist eine Möglichkeit, darüber nachzudenken, die Sie in mindestens eine Richtung (oder alternativ eine wilde Jagd) führen könnte. Trennen Sie die zwei Fragen und entfernen Sie überlappende Ergebnisse:

(1) Wie viele j-digit Zahlen sind teilbar durch k? [j 9's/k] - [(j-1) 9's/k]

(2) Wie viele j-digit Nummern enthalten die Ziffer k? 9 * 10^(k-1) - 8 x 9^(k-1)

Jetzt müssen wir die j-digit Zahlen subtrahieren, die beide teilbar durch k und umfassen die Ziffer k sind. Aber wie viele gibt es?

Verwenden Sie Teilbarkeitsregeln, um die verschiedenen Fälle zu berücksichtigen. Zum Beispiel:

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. 

(Nachtrag:. Ich die kombinatorische Frage auf math.stackexchange fragte und bekam einige interessante answers Und hier ist ein Link auf die Frage des OP auf math.stackexchange: https://math.stackexchange.com/questions/1884303/the-n-th-number-that-contains-the-digit-k-or-is-divisible-by-k-2-le-k-l)

Answer 2

Im Anschluss an גלעד ברקן's answer, wenn Sie eine O (1) Art der Berechnung haben d(j, k) = Zahlen mit mindestens einer Ziffer k bis j, verwerfen Zahlen, die durch k teilbar sind, dann können Sie berechnen e(j, k) = Zahlen mit mindestens auf Ziffer k oder teilbar durch k unter j als j/k + d(j, k).

Auf diese Weise können Sie f(n, k) mit binären Suche finden, da k <= f(n, k) <= k*n und e(j, k) = n <=> f(n, k) = j: Sie versuchen, im Wesentlichen zu erraten, welche j würde die erwartete n, in O (log n) ergeben versucht.

Ich stimme der גגעד בבקן Beobachtung in Bezug auf Teilbarkeitsregeln für die Berechnung d(j, k) effizient; aber sie sind nicht trivial zu implementieren, außer für k=5 und k=2.

Ich bezweifle stark, dass Sie O (log n) für dieses Problem verbessern können; und es kann für einige Werte von k nicht einmal erreichbar sein.

Answer 3

Dies ist komplexer als ich dachte, aber ich denke, ich habe eine Lösung für den einfachsten Fall (k = 2) gefunden.

Zuerst habe ich versucht, mit der Frage, die folgende Frage zu vereinfachen: Welche Position in der Folge haben die Nummern 10^i * k wo i = 1, 2, 3, ...? Für k = 2 sind die Zahlen 20, 200, 2000, ...

i k                 n 
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 der letzten Zeile ich das Muster auszudrücken versucht. Der erste Teil ist die Zahl, die durch 2 teilbar ist. Dann gibt es i-1 zusätzliche Teile für die ungeraden Zahlen mit einer 2 an der ersten Position, der zweiten und so weiter. Der schwierige Teil besteht darin, die Faktoren zu berechnen (2, 18, 162, ...).

Hier ist eine Funktion, um den neuen Faktor für jede i Rückkehr:

f(i) = 2 * 10^(i-2) - sum(10^(i-x-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 

So mit diesen Daten erstellen wir mit dem folgenden Algorithmus kann kommen:

Finden Sie die höchste Zahl 10^i*2, die nicht die Position nicht überschreitet . (Wenn n im Bereich [positionOf(10^i*2), positionOf(10^i*2) + (10^i)] liegt, dann kennen wir bereits die Lösung: 10^i*2 + (n - positionOf(10^i*2)). Wenn wir zB i = 2 finden, wissen wir, dass die nächsten 100 Werte alle in der Reihenfolge [201, 300] sind, also wenn 110 < = n < = 210, dann ist die Lösung 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; 

Diese Pseudo-Code nur ungetestet uncomplete ist (ich weiß, dass Sie nicht ^ in Java) verwenden können, ii = 1 oder 0 muss als Spezialfall behandelt werden, dieser fehlt und wie man i findet, wird auch nicht angezeigt oder die Antwort würde zu lang werden.