Déterminez s'il existe un sous-groupe contigu de longueur > 1 avec une moyenne entière.

Question

Étant donné un tableau non trié d'entiers.

J'essaie de trouver une solution efficace (meilleure que O(n 2 )) mais le mieux que j'ai pu trouver est une solution O(n 2 ) :

for i from 0 to size of list:
    sum = list[i]

    for j from i + 1 to size of list:
        sum += list[j]

        if sum % (j - i + 1) == 0:
            return true
return false

J'ai lu des articles sur la technique de la fenêtre glissante, mais il semble qu'elle ne soit utile que pour les sous-réseaux d'une longueur spécifique. k .

Answer 1

C'est peut-être une question piège :) La somme de deux nombres impairs donne un nombre pair et la somme de deux nombres pairs donne un nombre pair. Le seul ensemble de données qui ne comprendrait pas un sous-groupe contigu de longueur deux qui est également divisible par deux devrait alterner [..., odd, even, odd, even, ...] . Mais il faudrait alors restreindre encore davantage l'ensemble de données pour empêcher qu'un sous-groupe de longueur 4 soit divisible par quatre, puisque tous les autres nombres pairs sont divisibles par quatre.

La probabilité de recevoir une telle liste est extrêmement faible et continue de diminuer au fur et à mesure que la liste s'allonge (de plus, elle se prête à un sous-ensemble de motifs numériques ; ceux-ci pourraient-ils être intéressants ?), ce qui signifie qu'à moins que quelqu'un ne travaille minutieusement à en créer, la plupart, sinon toutes les situations du monde réel trouveraient une solution avec une fenêtre coulissante de taille 4 qui vérifie également la parité alternée.