Anzahl der Einsen im Ergebnis von 11 berechnen^

Question

Das folgende Problem wurde in einem Interview gestellt. Geben Sie eine Zahl 11 ⁿ (wobei n ÷ [0, 1000]), erhalten Sie die Anzahl der 1 s im Ergebnis. Zum Beispiel n = 3, 11 = 1331, so würde das erwartete Ergebnis seine 2. Oder bei n = 6, 11 = 1.771.561, würde das erwartete Ergebnis 3.

Mein erster Gedanke war dass es etwas mit dem pascal's triangle und binomial coefficients zu tun hatte (denn wie wir wissen, funktioniert pow(11, 1000) einfach nicht, zumindest in C).

Ich dachte durch einfaches Iterieren über die Spalten im Pascal-Dreieck sollte mir das Ergebnis geben, aber das funktioniert eindeutig nicht.

Also bin ich irgendwie jetzt fest. Mein nächster Gedanke war, eine Art von bignum library zu verwenden, um das Problem zu lösen, aber meiner Meinung nach muss es einen anderen Weg geben, um diese Art von Aufgabe zu lösen.

Update Ich habe vergessen zu erwähnen, dass ich diese Aufgabe mit C/Objective-C lösen sollte.

Answer 1

Wie Bartosz vorgeschlagen, ich würde dieses Problem lösen, indem einfach die Berechnungen in der Basis 10 10 kann eine Multiplikation mit 11 in der Basis der Durchführung mit getan werden eine Linksverschiebung und eine Addition. Hier ist ein C-Programm, das mit ASCII-Strings arbeitet. Beachten Sie, dass die niedrigstwertige Ziffer in jeder Zeichenfolge zuerst steht.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

char *multiply_by_11(const char *num, int *num_ones_ptr) 
{ 
    size_t len = strlen(num); 
    char *result = (char *)malloc(len + 3); 
    int carry = 0; 
    int num_ones = 0; 
    size_t i; 

    for (i = 0; i <= len; ++i) { 
     int digit = carry; 

     if (i < len) { 
      digit += num[i] - '0'; 
     } 
     if (i > 0) { 
      digit += num[i-1] - '0'; 
     } 

     if (digit < 10) { 
      carry = 0; 
     } 
     else { 
      digit -= 10; 
      carry = 1; 
     } 

     if (digit == 1) { 
      ++num_ones; 
     } 
     result[i] = digit + '0'; 
    } 

    if (carry) { 
     result[i++] = '1'; 
     ++num_ones; 
    } 

    result[i] = '\0'; 

    *num_ones_ptr = num_ones; 
    return result; 
} 

int main() 
{ 
    char *num = (char *)malloc(2); 
    int i; 

    strcpy(num, "1"); 

    for (i = 1; i <= 1000; ++i) { 
     int num_ones; 

     char *product = multiply_by_11(num, &num_ones); 
     printf("11^%4d: %3d ones\n", i, num_ones); 

     free(num); 
     num = product; 
    } 

    free(num); 
    return 0; 
} 

Answer 2

Haben sie Ihnen gesagt, wie effizient der Algorithmus sein sollte?

Ich würde es einfach auf Strings implementieren; Multiplikation mit 11 ist einfach eine Kopie mit einem nachgestellten 0 hinzugefügt und dann hinzufügen, so alles, was Sie tun müssten, implementieren das Hinzufügen von Zahlen als Strings geschrieben.

Answer 3

angenommen, K (i) ist eine Zeichenfolge, die aus der k-ten Zeile des Pascal-Dreiecks erzeugt wird.

11^0 = 1,11^1 = 11,11^2 = 121. Aber 11^i = k (i) ist eine falsche Annahme. Da 11^i = (10 + 1)^i &

====>

so für kleine Zahlen es wahr ist, weil 10^i ist sehr größer als a [i] für große Zahlen es hat vielleicht einen Überlauf aus dem folgenden Grund.

a[i+1]=((n-i+1)/a[i])*a[i]  
     & 
suppose that: a[i]*10^(n-i+1) and a[i+1]*10^(n-i) are two Consecutive numbers 

so wenn a[i]*10^(n-i+1) < a[i+1]*10^(n-i) Überlauf passiert. Indem Sie diese vereinfachen, erhalten Sie (n-i+1)/i >10, wenn Überlauf auftritt.
sollten Sie diese Überläufe in Ihrem Algorithmus berechnen.

Answer 4

Eine String-Version in Haskell scheint ganz gut zu funktionieren:

Prelude> let f n = length . filter (=='1') . show . (11^) $ n 
Prelude> f 1000 
105 
(0.00 secs, 1129452 bytes) 
Prelude> f 1000000 
104499 
(2.64 secs, 69393408 bytes)