Le tableau donné est trop grand et contient environ 10 ^ 6 éléments.
Je connais déjà la manière traditionnelle de parcourir chaque paire possible, mais je veux une manière / une astuce plus efficace.
int prod = 0, arr[]= {1,4};
for(int x = 0; x<arr.length;x++) {
for(int y = x;y<arr.length; y++) {
prod += arr[x] & arr[y];
}
}
System.out.println(prod);
3 Réponses :
Si arr [x] = 0, vous pouvez ignorer toute la boucle interne pour cette valeur de x (puisque 0 & y = 0 peu importe ce que y est.
La diagonale est une identité.
prod = 0;
for(int x = 0; x < arr.length; x++) {
int ax = arr[x];
for(int y = x + 1; y <arr.length; y++) {
prod += ax & arr[y];
}
prod += arr[x];
}
// Count the occurrences of each bit
int[] bitcounts = new int[32];
for (int x=0; x<arr.length; ++x) {
int val = arr[x];
for (int bit=0; bit<32; ++bit) {
if ((val & (1<<bit)) != 0) {
bitcounts[bit]++;
}
}
}
// If a bit appears in n entries, then it appears in n(n+1)/2 pairs
// (counting the pair of each item with itself)
int result = 0;
for (int bit=0; bit<32; ++bit) {
long pairs = ((long)bitcounts[bit]) * (bitcounts[bit]+1) / 2;
result += ((int)pairs) * (1<<bit);
}
return result;
Cette méthode ne fournit pas le résultat approprié. Voici un exemple: S'il y a un ARRAY = {1,2,3} alors RESULT doit être 9. EXPLICATION: And-product (1,1) + And-product (1,2) + And-product (1, 3) + Et-produit ct (2,2) + Et-produit ( 2,3) + Et-produit (3,3).
Oh, si vous voulez compter la diagonale, alors son n (n + 1) / 2. Je vais ajuster le code
Remercier! maintenant cela fonctionne correctement et c'est aussi le moyen le plus rapide que j'ai trouvé à ce jour.
Pourquoi est-ce étiqueté python-3.x ?
Vous évitez déjà les doublons de calcul sur la diagonale, et je pense que toute optimisation supplémentaire pourrait dépendre de l'apparence des données du tableau.
@JacobG. Je veux que ce soit fait en python ou en java.
Pourquoi le titre (et le nom de la variable) dit-il produit lorsque l'opérateur est
+ =?