Calcola il conteggio di quelli risultanti da 11^n

Question

In un'intervista è stato chiesto il seguente problema. Dato un numero 11 ⁿ (dove n ∈ [0, 1000]), ottenere il conteggio di 1 s nel risultato. Ad esempio, n = 3, 11 = 1331, in modo che il risultato atteso sarebbe 2. O dato n = 6, 11 = 1.771.561, il risultato atteso sarebbe 3.

Il mio primo pensiero è stato che doveva fare qualcosa con il pascal's triangle e binomial coefficients (perché come sappiamo semplicemente il calcolo di pow(11, 1000) non funziona, almeno in C).

Ho pensato semplicemente iterando sulle colonne nel triangolo di Pascal, dovrei darmi il risultato, ma chiaramente non funziona.

Quindi in questo momento sono bloccato. Il mio prossimo pensiero è stato quello di utilizzare una specie di bignum library per risolvere il problema, ma a mio parere ci deve essere un altro modo per risolvere questo tipo di compito.

Aggiornamento ho dimenticato di dire che avrei dovuto risolvere questo compito con C/Objective-C.

Answer 1

Come Bartosz suggerito, Vorrei risolvere questo semplicemente eseguendo i calcoli in base 10. Una moltiplicazione per 11 nella base 10 può essere fatto con uno spostamento a sinistra e un'aggiunta. Ecco un programma C che funziona su stringhe ASCII. Si noti che la cifra meno significativa viene prima di ogni stringa.

#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

Ti hanno detto quanto dovrebbe essere efficace l'algoritmo?

Lo implementerei direttamente sulle stringhe; moltiplicando per 11 è semplicemente facendo una copia con uno 0 finale aggiunto e quindi aggiungendo, quindi tutto ciò che devi fare è implementare l'aggiunta di numeri scritti come stringhe.

Answer 3

supporre che K (i) sia una stringa prodotta dalla riga k-esima del triangolo pascal.

11^0 = 1,11^1 = 11,11^2 = 121. Ma 11^i = k (i) è una falsa ipotesi. Perché 11^i = (10 + 1)^i &

====>

quindi per piccoli numeri è vero perché 10^i è molto più grande di un [i] per i grandi numeri potrebbe avere un overflow per il seguente motivo.

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 

quindi quando si verifica un overflow a[i]*10^(n-i+1) < a[i+1]*10^(n-i). Semplificando quelli, si ottiene (n-i+1)/i >10 che è quando avviene l'overflow.
dovresti calcolare questi overflow nell'algoritmo.

Answer 4

Una versione stringa in Haskell sembra funzionare bene:

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)