Bien que ce soit étrange de voir cette question, j'ai vraiment besoin de comprendre certains concepts de base pendant que je continue mon voyage de codage. J'ai un problème qui se trouve sur Hackerrank, il va comme: DIVISIBLE SUM PAIRS a > Je vais quand même donner l'énoncé du problème ici: Énoncé du problème Étant donné un tableau, où nous devons trouver le nombre de paires divisibles par le nombre donné k , et il y a une autre condition, qui est:
l'arr [i] Par exemple, Code Avant de publier mon code, j'aimerais vous dire que mon code a réussi tous les cas de test et qu'il est accepté de passer au défi suivant, mais il y a un problème qui J'essaye de comprendre, qui est là dans le code. Ici quand je fais ceci Quelqu'un peut-il m'aider à résoudre ce problème, comme ce qui reste. Puisque je sais que la vérification MODIFICATIONS Depuis que j'ai compris ce que je faisais de travers. Et j'ai une modification dans mon code qui ne démarre pas la boucle interne avec 1 , car elle commencera par 1 à chaque fois que la boucle interne se terminera et s'exécutera à nouveau. Je remercie tous ceux qui m'ont aidé à clarifier cela et à rendre mes concepts suffisamment forts pour traiter les questions de cette manière. Je remercie personnellement Mike 'Pomax' Kamermans , Ricola et xerx593 pour effacer mon doutes, et me donnant les concepts de base de la boucle à travers les éléments. Cela m'aidera à l'avenir, et je ne le répéterai plus. :) ar = [1,2,3,4,5,6] et k = 5 . Nos trois paires remplissant les critères sont [1,4] [2,3] et [4,6 .static int divisibleSumPairs(int n, int k, int[] ar) {
int count = 0;
for(int i=0; i<ar.length; i++){
for(int j=i+1; j<ar.length; j++){
if(((ar[i]+ar[j])%k)==0){
if(i < j)
count++;
}
}
}
return count;
}
if (i if (ar [i] , cela me donne supposément une mauvaise réponse. arr [i]
5 Réponses :
Je viens de vérifier votre lien et la condition donnée dans l'énoncé de question est
Trouvez et affichez le nombre de (i, j) paires où i
Qui est simplement le nombre de paires non ordonnées d'éléments pour lesquels le la somme est divisible par k.
Quelle que soit la manière dont vous avez écrit
il y a une autre condition, qui est: le arr [i]
de ces paires.
Il semble que vous ayez mal lu la question. Et cela explique pourquoi la condition i arr [i]
Maintenant que vous savez que vous n'avez besoin que des paires non ordonnées, pas besoin d'itérer j de 1 à ar.length . Puisque vous avez besoin de j> i , chaque j entre 1 et i (inclus) est inutile. Vous pouvez simplifier votre code en:
static int divisibleSumPairs(int n, int k, int[] ar) {
int count = 0;
for(int i=0; i<ar.length-1; i++){
for(int j=i+1; j<ar.length; j++){
if(((ar[i]+ar[j])%k)==0){
count++;
}
}
}
return count;
}
Oui @Ricola J'ai relu la question, et il semble que i
cf. Commentaire de Pomax à OP
Lorsque vous faites il me donne supposément une mauvaise réponse ... il vous donne correctement la mauvaise réponse! ... depuis quand Si vous n'incluez pas le Un (implémentation) alternative serait: ... pour initialiser la boucle interne avec MODIFIER: (après avoir mieux répondu à la question) Votre hypothèse, que i = {0 ... 10} et j = {1 ... 10} , alors il y a (environ) 100 cmobinations (sur i et j), (environ) 50, où i a [i] + a [j]% k == 0 , alors a [j] + a [i]% k == 0 aussi ! if (i for (int i = 0; i < ar.length; i++) {
// ensure i < j via initialization ;)
for (int j = i + 1; j < ar.length; j++) {
if (((ar[i]+ar[j]) % k) == 0) {
counter++;
}
}
}
i + 1 au lieu de 1 code >.
a [i]> a [j] est équivalent avec i> j OU j (mais pas les deux), est presque correct: sauf quand a [i] == a [j] code >.
J'obtiens la même réponse, puisque la boucle suit uniquement la forme pos 1, qui est en fait i + 1 dans ce cas. Vous pouvez exécuter ma logique et utiliser le j = 1 , vous obtiendrez le même résultat. Depuis que je devais le comparer avec le système de bouclage normal. N'apporte cependant aucun changement. Merci pour votre contribution
@Alok ce n'est pas vrai, 1 n'est pas i + 1 . La seule raison pour laquelle cela ne fait aucune différence est à cause de votre condition if (i
..ok, maintenant peut-être mieux comprendre la question ... a [i]> a [j] est "presque équivalent" avec i> j ou (vice versa: ) ... mais vous n'avez pas considéré le cas d'angle !!!
@ xerx593: attendez quoi? Les deux conditions ne sont pas du tout équivalentes. Ils ne le sont que si et seulement si le tableau est trié dans un ordre strictement croissant.
non, pas équivalent, @Ricola mais pour cet algorithme ... (invariant de boucle, pour compter correctement (et exclure les doublons .. comme dans la boucle d'origine))
Vous avez votre point @ xerx593, car à chaque fois, la boucle interne ne démarrera qu'à partir de 1, ce qui est complètement faux. Nous devons toujours commencer par l'élément suivant de l'élément i.
... je comprends maintenant, l'hypothèse d'alok, et pourquoi c'est faux :)
@ xerx593: ok je comprends, vous voulez dire dans ce cas précis où i> j signifie simplement "paire non ordonnée"? (Dans le même ordre d'idées, puisqu'il suffit de compter les paires, la condition i
Cette solution utilise javaScript:
divisibleSumPairs (n, k, ar) => {
let count = 0;
ar = ar.map((value, index, arr) => {
for (let i = index + 1; i <= arr.length; i++) {
if ((value + arr[i]) % k === 0) {
count++;
}
}
});
return count
}
Une solution en Python 3 (passé tous les cas de test):
Le itertools.combinations (arr, r) retourne les r sous-séquences de longueur des éléments de l'itérable d'entrée. Les combinaisons sont émises dans l'ordre de tri lexicographique. Donc, si l'entrée itérable est triée, les tuples de combinaison seront produits dans l'ordre trié.
from itertools import combinations
def divisibleSumPairs(n,ar,k):
pairs = []
for com in combinations(ar,2):
if sum(com) % k == 0:
pairs.append(com)
return len(pairs)
nk = input().split()
n = int(nk[0])
k = int(nk[1])
ar = list(map(int, input().rstrip().split()))
print(divisibleSumPairs(n,ar,k))
C'est ma solution en javaScript (passé tous les cas de test):
function divisibleSumPairs(n, k, ar) {
let count=0;
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
if(i<j){
if((ar[i]+ar[j])%k===0) count++;
}
}
}
return count;
}
étant donné la condition arr [i] j = 1 chaque fois que vous exécutez la boucle interne, au lieu de
j = i + 1?N'est-ce pas la même chose que
j = 1, eti = 0, car de toute façon il sera devant lei, à droite @Mike ' Pomax'Kamermans?Pas du tout, et vous pouvez le vérifier en écrivant ce que fait le code suivant, à la main, sur du papier ou dans un éditeur de texte ou quelque chose:
for (i = 0; i <3; i ++) {for ( j = 1; j <3; j ++) {imprimer i + "/" + j; }}. Commencez pari = 0, quelles paires verrez-vous imprimées? Puisiincréments, maintenant quelles paires verrez-vous imprimées?Correction du problème:. . . trouver le nombre de paires dont la somme est divisible par le nombre k donné. . .