C++: Zéros de fin de multiplication de tableau

Étant donné un tableau A, je dois multiplier tous les éléments de tableau. Puisque les nombres peuvent aller jusqu'à 10^9, je dois trouver les zéros traînants du produit. J'ai fait ce qui suit:C++: Zéros de fin de multiplication de tableau

int ans= 0; // to count no of trailing zeroes 
for(long int i =0; i<n ; i++) // n can be very large(upto 10^5) 
{ 
    long long int p=1; 
    p=p*a[i]; 
    while (p2℅10 ==0) 
    { ans++; 
    p=p/10; 
    } 
}

La fonction permettant de calculer le nombre de 2 est la suivante. J'ai remplacé 2 par 5 pour calculer nunber de 5.

Int nm2(long long a) 
{ 
    Int b=0; 
    while(a℅2==0){ 
    a=a/2; 
    b++; 
    } 
    return b; 
    } 

Int p2=0,p5=0; 
For(long long i=L;i<R;i++) 
{ 
    p2 += nm2(a[i]); 
    p5 += nm5 (a[i]); 
    } 
Int ans += min(p2,p5); // storing no of zeroes every time I multiply elements of array from Index L to Index R of array a[].

Comment puis-je l'améliorer? Ou y a-t-il d'autres façons de le calculer avec une efficacité plus rapide? Sil te plait aide moi.

Source

2016-10-12 Sam_Buck

Cela ressemble à la manière la plus efficace possible pour moi. Les changements sont plus rapides que les divisions, mais je ne vois pas comment exploiter cela ici. Je pense que vous l'avez cloué, personnellement, et j'ai hâte de voir ce que les autres disent. Bonne question! – allen1

FWIW, si vous êtes * vraiment * concerné par l'efficacité, http://stackoverflow.com/questions/12356442/binary-divisibility-by-10; voir aussi ici: http://stackoverflow.com/questions/7070346/c-best-way-to-get-integer-division-and-remainder BTW, est-ce l'indentation que vous utilisez dans votre code actuel? – vaxquis

@vaxquis Cette méthode ne sera-t-elle pas longue? Convertir un long long en binaire, puis ces manipulations de bits, puis en calculant le nombre de zéros. ? Je ne suis pas bon mais cela semble long. –

Ceci est plus sur la théorie des nombres que sur les détails de la division. Voici ce que je ferais

int fives = 0; 
int twos = 0; 

for (int i=0; i<n; i++) { 
    fives += countFives(a[i]); 
    twos += countTwos(a[i]); 
} 

int trailingZeros = fives > twos ? twos : fives;

Les deux fonctions countTwos et countFives sont assez simples, et je compte le nombre de facteurs de 2 et 5, respectivement, d'une valeur d'entrée donnée.

La ligne qui calcule le nombre de zéros finaux est basée sur le fait que chaque zéro doit être dû exactement à un facteur 2 et un facteur 5. Si vous avez plus de 2 que de 5, ils ne contribueront pas zéros, et vice versa. Ainsi, le nombre de zéros finaux est égal au plus petit des deux nombres.

Source

2016-10-12 20:47:17

Je l'ai fait exactement au début, mais pour les nombres longs, la réponse est fausse. dans le tableau avant cette multiplication finale mais j'ai mis à jour le nombre de 2 et 5 chaque fois qu'une mise à jour a été faite dans le tableau.C'est pourquoi je devais faire la division mais avec cela je dépasse la limite de temps –

Pouvez-vous me donner un exemple? l'algorithme donne un résultat incorrect, je suis confiant qu'il est correct. Pour être arrogant, mais chaque zéro final doit être dû à un facteur de 10 = 2 * 5, le nombre de zéros finaux est égal au nombre de 2 facteurs qui "correspondent" à un facteur 5. –

Pouvez-vous poster votre algorithme qui compte des facteurs de 2 et 5 ?, afin que je puisse voir ce que vous faisiez? –

N'est ce pas ce que la notation scientifique est pour quand vous faites face à un très grand nombre?

Aucune raison pour laquelle vous avez besoin de zéros de fin, mais std :: scientific pourrait vous aider à exprimer de très grands nombres.

Source

2016-10-12 22:46:34 user6590212

Non, j'ai juste besoin du nombre de zéros de fin. –

Convertit le nombre en une chaîne et compte à partir de la fin de celle-ci. ou imprimez le résultat dans un fichier. puis comptez-les quand vous l'avez stocké dans un fichier. – user6590212

la réponse aura plus de 18 nombre de chiffres stockant ainsi cette grande réponse à chaque fois et faire cela plusieurs fois sera très agité et lent. Voilà pourquoi j'essaie d'utiliser le nombre de 2 et 5. –

C++: Zéros de fin de multiplication de tableau

Répondre

Questions connexes