Algorithme pour déterminer si le tableau contient n… n + m?

J’ai vu cette question sur Reddit, et il n’y avait pas de solutions positives présentées, et j’ai pensé que ce serait une question parfaite à poser ici. C’était dans un fil de discussion sur les questions d’entretien:

Écrivez une méthode qui prend un tableau int de taille m et renvoie (True / False) si le tableau est constitué des nombres n … n + m-1, tous les nombres de cette plage et uniquement les nombres de cette plage. Le tableau n’est pas garanti pour être sortingé. (Par exemple, {2,3,4} retournerait vrai. {1,3,1} retournerait faux, {1,2,4} retournerait faux.

Le problème que j’ai eu avec celui-ci est que mon interlocuteur m’a demandé d’optimiser (plus vite O (n), moins de mémoire, etc.), au sharepoint prétendre pouvoir le faire en un seul passage en utilisant une quantité constante de Mémoire. Je n’ai jamais compris ça.

Avec vos solutions, veuillez indiquer si elles supposent que le tableau contient des éléments uniques. Indiquez également si votre solution suppose que la séquence commence à 1. (J’ai légèrement modifié la question pour autoriser les cas où elle va 2, 3, 4 …)

edit: Je suis maintenant d’avis qu’il n’existe pas d’algorithme linéaire dans le temps et constant dans l’espace qui gère les doublons. Quelqu’un peut-il vérifier cela?

Le problème de duplication se résume à tester pour voir si le tableau contient des doublons dans O (n) time, O (1) space. Si cela peut être fait, vous pouvez simplement tester d’abord et s’il n’y a pas de doublons, exécutez les algorithmes publiés. Alors, pouvez-vous tester les dupes dans l’espace O (n) time O (1)?

Sous l’hypothèse que les nombres inférieurs à un ne sont pas autorisés et qu’il n’y a pas de doublons, il existe une identité de sommation simple – la sum des nombres de 1 à m par incréments de 1 est (m * (m + 1)) / 2 . Vous pouvez ensuite additionner le tableau et utiliser cette identité.

Vous pouvez savoir s’il y a un dupe en vertu des garanties ci-dessus, plus la garantie si aucun numéro n’est supérieur à m ou inférieur à n (ce qui peut être vérifié dans O(N) )

L’idée en pseudo-code:
0) Démarrer à N = 0
1) Prenez le N-ème élément de la liste.
2) S’il n’est pas au bon endroit si la liste a été sortingée, vérifiez où il devrait se trouver.
3) Si le lieu où il devrait être a déjà le même numéro, vous avez un dupe – RETURN TRUE
4) Sinon, échangez les numéros (pour mettre le premier numéro au bon endroit).
5) Avec le numéro que vous venez de changer, est-ce que c’est au bon endroit?
6) Si non, revenez à la deuxième étape.
7) Sinon, commencez par la première étape avec N = N + 1. Si cela dépasse la fin de la liste, vous n’avez pas de dupes.

Et, oui, cela fonctionne dans O(N) bien que cela puisse ressembler à O(N ^ 2)

Note à tous (éléments recueillis à partir de commentaires)

Cette solution fonctionne sous l’hypothèse que vous pouvez modifier le tableau, puis utilise le sorting sur Radix sur place (qui atteint la vitesse O(N) ).

D’autres solutions mathématiques ont été proposées, mais je ne suis pas sûr qu’elles aient été prouvées. Il y a un tas de sums qui peuvent être utiles, mais la plupart d’entre elles se heurtent à une augmentation du nombre de bits requirejs pour représenter la sum, ce qui va à l’encontre de la garantie d’espace supplémentaire constante. Je ne sais pas non plus si l’un d’entre eux est capable de produire un nombre distinct pour un ensemble de nombres donné. Je pense qu’une sum de carrés pourrait fonctionner, qui a une formule connue pour le calculer (voir Wolfram )

Nouvel aperçu (enfin, plus de reflections qui ne permettent pas de le résoudre, mais qui sont intéressantes et que je vais au lit):

Donc, il a été mentionné que peut-être utiliser sum + sum de carrés. Personne ne savait si cela fonctionnait ou non, et j’ai réalisé que cela ne devient un problème que lorsque (x + y) = (n + m), comme le fait 2 + 2 = 1 + 3. Les carrés ont aussi ce problème grâce à Les sortingples pythagoriciens (donc 3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2 et la sum des carrés ne fonctionnent pas). Si nous utilisons le dernier théorème de Fermat , nous soaps que cela ne peut pas arriver pour n ^ 3. Mais nous ne soaps pas non plus s’il n’y a pas x + y + z = n pour cela (sauf si nous le faisons et que je ne le sais pas). Donc, rien ne garantit que cela ne se rompt pas – et si nous continuons dans cette voie, nous sums rapidement à court de bits.

Dans ma joie, cependant, j’ai oublié de noter que vous pouvez casser la sum des carrés, mais vous créez ainsi une sum normale qui n’est pas valide. Je ne pense pas que vous puissiez faire les deux, mais, comme on l’a noté, nous n’avons pas de preuve dans les deux cas.


Je dois dire que trouver des contre-exemples est parfois beaucoup plus facile que de prouver des choses! Considérons les séquences suivantes, qui ont toutes une sum de 28 et une sum de carrés de 140:

 [1, 2, 3, 4, 5, 6, 7] [1, 1, 4, 5, 5, 6, 6] [2, 2, 3, 3, 4, 7, 7] 

Je n’ai pas pu trouver de tels exemples de longueur 6 ou moins. Si vous voulez un exemple qui a aussi les valeurs min et max correctes, essayez celle de longueur 8:

 [1, 3, 3, 4, 4, 5, 8, 8] 

Une approche plus simple (en modifiant l’idée de hazzen):

Un tableau entier de longueur m contient tous les nombres de n à n + m-1 exactement une fois

  • chaque élément du tableau est compris entre n et n + m-1
  • il n’y a pas de doublons

(Reason: il n’y a que m valeurs dans la plage entière, donc si le tableau contient m valeurs uniques dans cette plage, il doit en contenir une fois)

Si vous êtes autorisé à modifier le tableau, vous pouvez vérifier les deux en une seule fois dans la liste avec une version modifiée de l’idée de l’algorithme de hazzen (il n’ya pas besoin de faire la sum):

  • Pour tous les index de tableau de 0 à m-1
    1. Si tableau [i] = n + m => RETURN FALSE (“valeur hors plage trouvée”)
    2. Calculer j = tableau [i] – n (il s’agit de la position basée sur 0 du tableau [i] dans un tableau sortingé avec des valeurs de n à n + m-1)
    3. Alors que j n’est pas égal à i
      1. Si la liste [i] est égale à list [j] => RETURN FALSE (“duplicate found”)
      2. Liste d’échange [i] avec liste [j]
      3. Recalculez j = tableau [i] – n
  • RETOUR VRAI

Je ne suis pas sûr si la modification du tableau d’origine compte avec l’espace maximum autorisé de O (1), mais si ce n’est pas le cas, cela devrait être la solution souhaitée par l’affiche.

En travaillant avec a[i] % a.length au lieu d’ a[i] vous réduisez le problème à la nécessité de déterminer que vous avez les nombres 0 à une a.length - 1 .

Nous prenons cette observation pour acquise et essayons de vérifier si le tableau contient [0, m].

Trouvez le premier noeud qui n’est pas dans la bonne position, par exemple

 0 1 2 3 7 5 6 8 4 ; the original dataset (after the renaming we discussed) ^ `---this is position 4 and the 7 shouldn't be here 

Échangez ce numéro là où il devrait être. à savoir échanger le 7 avec le 8 :

 0 1 2 3 8 5 6 7 4 ; | `--------- 7 is in the right place. `--------------- this is now the 'current' position 

Maintenant, nous répétons ceci. En regardant à nouveau notre position actuelle, nous demandons:

“Est-ce le bon numéro pour ici?”

  • Sinon, nous le remplaçons au bon endroit.
  • Si c’est au bon endroit, nous allons à droite et recommençons.

Suite à cette règle, nous obtenons:

 0 1 2 3 4 5 6 7 8 ; 4 and 8 were just swapped 

Cela va progressivement construire la liste correctement de gauche à droite, et chaque numéro sera déplacé au maximum une fois, et donc ceci est O (n).

S’il y a des dupes, nous le remarquerons dès qu’il y aura une tentative d’échanger un numéro dans la liste.

Pourquoi les autres solutions utilisent-elles une sum de toutes les valeurs? Je pense que cela est risqué, car lorsque vous ajoutez O (n) éléments en un seul numéro, vous utilisez techniquement plus de O (1) espace.

Méthode plus simple:

Étape 1, déterminer s’il y a des doublons. Je ne suis pas sûr que cela soit possible dans l’espace O (1). Quoi qu’il en soit, retournez false si des doublons sont présents.

Étape 2, parcourez la liste, suivez les éléments les plus bas et les plus élevés .

Étape 3, Est-ce que (plus haut – plus bas) est égal à m? Si oui, retournez vrai.

Tout algorithme à un passage nécessite des bits de stockage Omega (n).

Supposons au contraire qu’il existe un algorithme à un passage qui utilise o (n) bits. Comme il ne fait qu’un seul passage, il doit résumer les premières valeurs n / 2 dans l’espace o (n). Comme il existe C (n, n / 2) = 2 ^ Thêta (n) ensembles possibles de n / 2 valeurs tirées de S = {1, …, n}, il existe deux ensembles distincts A et B de n / 2 valeurs telles que l’état de la mémoire est le même après les deux. Si A ‘= S \ A est l’ensemble “correct” de valeurs à compléter A, alors l’algorithme ne peut pas répondre correctement aux entrées

AA ‘- oui

BA ‘- non

car il ne peut pas distinguer le premier cas du second.

QED

Votez-moi si je me trompe, mais je pense que nous pouvons déterminer s’il y a des doublons ou non. Puisque nous connaissons la moyenne à l’avance (n + (m-1) / 2 ou quelque chose comme ça), nous pouvons simplement additionner les nombres et les carrés de différence pour voir si la sum correspond à l’équation (mn + m (m-1 ) / 2) et la variance est (0 + 1 + 4 + … + (m-1) ^ 2) / m. Si la variance ne correspond pas, il est probable que nous ayons un doublon.

EDIT: la variance est supposée être (0 + 1 + 4 + … + [(m-1) / 2] ^ 2) * 2 / m, car la moitié des éléments est inférieure à la moyenne et l’autre moitié est supérieure à la moyenne.

S’il existe un doublon, un terme de l’équation ci-dessus différera de la séquence correcte, même si un autre doublon annule complètement le changement de moyenne. La fonction ne retourne donc vrai que si la sum et la variance correspondent aux valeurs supprimées, ce que nous pouvons calculer au préalable.

Voici une solution de travail dans O (n)

Ceci utilise le pseudo-code suggéré par Hazzen et certaines de mes propres idées. Cela fonctionne aussi pour les nombres négatifs et ne nécessite pas de sum de carrés.

 function testArray($nums, $n, $m) { // check the sum. PHP offers this array_sum() method, but it's // sortingvial to write your own. O(n) here. if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) { return false; // checksum failed. } for ($i = 0; $i < $m; ++$i) { // check if the number is in the proper range if ($nums[$i] < $n || $nums[$i] >= $n + $m) { return false; // value out of range. } while (($shouldBe = $nums[$i] - $n) != $i) { if ($nums[$shouldBe] == $nums[$i]) { return false; // duplicate } $temp = $nums[$i]; $nums[$i] = $nums[$shouldBe]; $nums[$shouldBe] = $temp; } } return true; // huzzah! } var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5)); // true var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5)); // true var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5)); // false - out of range var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5)); // false - checksum fail var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5)); // false - dupe var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true 

Il y a quelque temps, j’ai entendu parler d’un algorithme de sorting très intelligent de la part de quelqu’un qui travaillait pour la compagnie de téléphone. Ils ont dû sortinger un grand nombre de numéros de téléphone. Après avoir passé en revue plusieurs stratégies de sorting, ils ont finalement trouvé une solution très élégante: ils ont simplement créé un tableau de bits et traité le décalage dans le tableau de bits comme numéro de téléphone. Ils ont ensuite parcouru leur firebase database avec un seul passage, changeant le bit pour chaque numéro à 1. Après cela, ils ont balayé le tableau de bits une fois, en crachant les numéros de téléphone pour les entrées dont le bit était haut.

Dans ce sens, je pense que vous pouvez utiliser les données du tableau comme une structure de métadonnées pour rechercher des doublons. Dans le pire des cas, vous pourriez avoir un tableau séparé, mais je suis sûr que vous pouvez utiliser le tableau d’entrée si cela ne vous dérange pas un peu de permutation.

Je vais laisser de côté le paramètre n pour le temps, b / c qui ne fait que confondre les choses – il est assez facile d’append un décalage d’index.

Considérer:

 for i = 0 to m if (a[a[i]]==a[i]) return false; // we have a duplicate while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i) sum = sum + a[i] next if sum = (n+m-1)*m return true else return false 

Ce n’est pas O (n) – probablement plus proche de O (n Log n) – mais il fournit un espace constant et peut fournir un vecteur d’attaque différent pour le problème.

Si nous voulons O (n), alors, en utilisant un tableau d’octets et certaines opérations sur les bits, nous fournirons le contrôle de duplication avec un n / 32 octets de mémoire supplémentaire (en supposant des bits de 32 bits, bien sûr).

EDIT: l’algorithme ci-dessus pourrait être amélioré en ajoutant la vérification de sum à l’intérieur de la boucle et vérifier:

 if sum > (n+m-1)*m return false 

De cette façon, il échouera rapidement.

En supposant que vous ne connaissiez que la longueur du tableau et que vous soyez autorisé à modifier le tableau, vous pouvez le faire dans les espaces O (1) et O (n).

Le processus comporte deux étapes simples. 1. “sortinger modulo” le tableau. [5,3,2,4] => [4,5,2,3] (O (2n)) 2. Vérifiez que le voisin de chaque valeur est un supérieur à lui-même (modulo) (O (n))

Tout ce dont vous avez besoin au plus 3 passes à travers le tableau.

Le sorting modulo est la partie «délicate», mais l’objective est simple. Prenez chaque valeur du tableau et stockez-la à sa propre adresse (longueur modulo). Cela nécessite un passage dans le tableau, en boucle sur chaque emplacement «en expulsant» sa valeur en le plaçant au bon endroit et en déplaçant la valeur à sa destination. Si vous déplacez une valeur correspondant à la valeur que vous venez d’expulser, vous avez un doublon et vous pouvez sortir plus tôt. Dans le pire des cas, c’est O (2n).

Le contrôle est un simple passage dans le tableau, examinant chaque valeur avec son voisin le plus proche. Toujours O (n).

L’algorithme combiné est O (n) + O (2n) = O (3n) = O (n)

Pseudocode de ma solution:

 foreach (valeurs []) 
   while (valeurs [i] non congru à i)
     à être expulsé = valeurs [i]
     expulser (valeurs [i]) // basculer vers sa position "correcte"
     si (valeurs [i]% longueur == à expulser% longueur)
       retourner faux;  // un "doublon" est arrivé quand nous avons expulsé ce nombre
   fin alors
 fin de foreach
 foreach (valeurs [])
   if ((valeurs [i] +1)% length! = valeurs [i + 1]% length)
     retourner faux
 fin de foreach

J’ai inclus la preuve de concept du code java ci-dessous, ce n’est pas joli, mais ça passe tous les tests unitaires que j’ai faits pour cela. Je les appelle un “StraightArray” parce qu’ils correspondent à la main de poker d’une suite (séquence contiguë ignorant la combinaison).

 public class StraightArray { static int evict(int[] a, int i) { int t = a[i]; a[i] = a[t%a.length]; a[t%a.length] = t; return t; } static boolean isStraight(int[] values) { for(int i = 0; i < values.length; i++) { while(values[i]%values.length != i) { int evicted = evict(values, i); if(evicted%values.length == values[i]%values.length) { return false; } } } for(int i = 0; i < values.length-1; i++) { int n = (values[i]%values.length)+1; int m = values[(i+1)]%values.length; if(n != m) { return false; } } return true; } } 

Implémentation de l’algorithme de Hazzen en C

 #include #define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j]; int check_ntom(int a[], int n, int m) { int i = 0, j = 0; for(i = 0; i < m; i++) { if(a[i] < n || a[i] >= n+m) return 0; //invalid entry j = a[i] - n; while(j != i) { if(a[i]==a[j]) return -1; //bucket already occupied. Dupe. swapxor(a, i, j); //faster bitwise swap j = a[i] - n; if(a[i]>=n+m) return 0; //[NEW] invalid entry } } return 200; //OK } int main() { int n=5, m=5; int a[] = {6, 5, 7, 9, 8}; int r = check_ntom(a, n, m); printf("%d", r); return 0; } 

Modifier: modification du code pour éliminer tout access illégal à la mémoire.

 boolean determineContinuousArray(int *arr, int len) { // Suppose the array is like below: //int arr[10] = {7,11,14,9,8,100,12,5,13,6}; //int len = sizeof(arr)/sizeof(int); int n = arr[0]; int *result = new int[len]; for(int i=0; i< len; i++) result[i] = -1; for (int i=0; i < len; i++) { int cur = arr[i]; int hold ; if ( arr[i] < n){ n = arr[i]; } while(true){ if ( cur - n >= len){ cout << "array index out of range: meaning this is not a valid array" << endl; return false; } else if ( result[cur - n] != cur){ hold = result[cur - n]; result[cur - n] = cur; if (hold == -1) break; cur = hold; }else{ cout << "found duplicate number " << cur << endl; return false; } } } cout << "this is a valid array" << endl; for(int j=0 ; j< len; j++) cout << result[j] << "," ; cout << endl; return true; } 
 def test(a, n, m): seen = [False] * m for x in a: if x < n or x >= n+m: return False if seen[xn]: return False seen[xn] = True return False not in seen print test([2, 3, 1], 1, 3) print test([1, 3, 1], 1, 3) print test([1, 2, 4], 1, 3) 

Notez que cela ne fait qu’un passage dans le premier tableau, sans tenir compte de la recherche linéaire impliquée dans not in . 🙂

J’aurais également pu utiliser un set Python, mais j’ai opté pour la solution simple où les caractéristiques de performances de l’ set n’ont pas à être sockets en compte.

Mise à jour: Smashery a souligné que j’avais mal analysé la “quantité constante de mémoire” et que cette solution ne résout pas le problème.

Si vous voulez connaître la sum des nombres [n ... n + m - 1] utilisez cette équation.

 var sum = m * (m + 2 * n - 1) / 2; 

Cela fonctionne pour n’importe quel nombre, positif ou négatif, même si n est une décimale.

Pourquoi les autres solutions utilisent-elles une sum de toutes les valeurs? Je pense que cela est risqué, car lorsque vous ajoutez O (n) éléments en un seul numéro, vous utilisez techniquement plus de O (1) espace.

O (1) indique un espace constant qui ne change pas par le nombre de n. Peu importe qu’il s’agisse de 1 ou 2 variables tant qu’il s’agit d’un nombre constant. Pourquoi dites-vous que c’est plus qu’un espace O (1)? Si vous calculez la sum de n nombres en l’accumulant dans une variable temporaire, vous utiliserez exactement 1 variable de toute façon.

Commenter dans une réponse parce que le système ne me permet pas encore d’écrire des commentaires.

Mise à jour (en réponse aux commentaires): dans cette réponse, j’entendais l’espace O (1) partout où “espace” ou “heure” était omis. Le texte cité fait partie d’une réponse antérieure à laquelle il s’agit d’une réponse.

Compte tenu de cela –

Ecrivez une méthode qui prend un tableau int de taille m …

Je suppose qu’il est juste de conclure qu’il existe une limite supérieure pour m, égale à la valeur du plus grand int (2 ^ 32 étant typique). En d’autres termes, même si m n’est pas spécifié en tant qu’int, le fait que le tableau ne puisse pas contenir de doublons implique qu’il ne peut y avoir plus que le nombre de valeurs pouvant être formées sur 32 bits, ce qui implique limité à être un int aussi.

Si une telle conclusion est acceptable, je propose d’utiliser un espace fixe de (2 ^ 33 + 2) * 4 octets = 34 359 738 376 octets = 34,4 Go pour traiter tous les cas possibles. (Sans compter l’espace requirejs par le tableau d’entrée et sa boucle).

Bien sûr, pour l’optimisation, je voudrais d’abord prendre en compte et allouer uniquement la quantité nécessaire (2m + 2) * 4 octets.

Si cela est acceptable pour la contrainte d’espace O (1) – pour le problème indiqué – alors laissez-moi procéder à une proposition algorithmique … 🙂

Hypothèses : tableau de m ints, positif ou négatif, aucun supérieur à ce que 4 octets peuvent contenir. Les doublons sont traités. La première valeur peut être n’importe quel int valide. Restreindre comme ci-dessus.

Tout d’abord , créez un tableau int de longueur 2m-1, ary , et fournissez trois variables int: left , diff et right . Notez que fait 2m + 2 …

Deuxièmement , prenez la première valeur du tableau d’entrée et copiez-la dans la position m-1 du nouveau tableau. Initialiser les trois variables.

  • set ary [m-1] – nthVal // n = 0
  • set left = diff = right = 0

Troisièmement , parcourez les valeurs restantes du tableau d’entrée et procédez comme suit pour chaque itération:

  • set diff = nthVal – ary [m-1]
  • if ( diff > m-1 + right || diff <1-m + left ) renvoie false // hors limites
  • if ( ary [m-1 + diff ]! = null) renvoie false // duplicate
  • définir ary [m-1 + diff ] = nthVal
  • si ( diff > gauche ) left = diff // contraintes gauche plus à droite
  • if ( diff < right ) right = diff // contraint droit lié plus à gauche

J’ai décidé de mettre cela dans le code, et cela a fonctionné.

Voici un exemple de travail utilisant C #:

 public class Program { static bool puzzle(int[] inAry) { var m = inAry.Count(); var outAry = new int?[2 * m - 1]; int diff = 0; int left = 0; int right = 0; outAry[m - 1] = inAry[0]; for (var i = 1; i < m; i += 1) { diff = inAry[i] - inAry[0]; if (diff > m - 1 + right || diff < 1 - m + left) return false; if (outAry[m - 1 + diff] != null) return false; outAry[m - 1 + diff] = inAry[i]; if (diff > left) left = diff; if (diff < right) right = diff; } return true; } static void Main(string[] args) { var inAry = new int[3]{ 2, 3, 4 }; Console.WriteLine(puzzle(inAry)); inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 }; Console.WriteLine(puzzle(inAry)); inAry = new int[3] { 21, 31, 41 }; Console.WriteLine(puzzle(inAry)); Console.ReadLine(); } } 

note : ce commentaire est basé sur le texte original de la question (il a été corrigé depuis)

Si la question est posée exactement comme écrit ci-dessus (et ce n’est pas juste une faute de frappe) et pour un tableau de taille n, la fonction devrait retourner (True / False) si le tableau est constitué des nombres 1 … n + 1,

… alors la réponse sera toujours fausse car le tableau avec tous les nombres 1 … n + 1 sera de taille n + 1 et non n. on peut donc répondre à la question dans O (1). 🙂

Contre-exemple pour l’ algorithme XOR .

(ne peut pas le poster en tant que commentaire)

@popopome

Pour a = {0, 2, 7, 5,} il retourne true (signifie que a est une permutation de la plage [0, 4) ), mais il doit retourner false dans ce cas ( a est évidemment pas une permutaton de [0, 4) ).

Un autre exemple de compteur: {0, 0, 1, 3, 5, 6, 6} – toutes les valeurs sont dans la plage mais il y a des doublons.

Je pourrais implémenter incorrectement l’idée de Popopome (ou les tests), donc voici le code:

 bool isperm_popopome(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no ressortingctions on n, no overflow, a[] may be readonly */ int even_xor = 0; int odd_xor = 0; for (int i = 0; i < m; ++i) { if (a[i] % 2 == 0) // is even even_xor ^= a[i]; else odd_xor ^= a[i]; const int b = i + n; if (b % 2 == 0) // is even even_xor ^= b; else odd_xor ^= b; } return (even_xor == 0) && (odd_xor == 0); } 

Version AC du pseudo-code de b3

(pour éviter une mauvaise interprétation du pseudo-code)

Exemple de compteur: {1, 1, 2, 4, 6, 7, 7} .

 int pow_minus_one(int power) { return (power % 2 == 0) ? 1 : -1; } int ceil_half(int n) { return n / 2 + (n % 2); } bool isperm_b3_3(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, doesn't use n possible overflow in sum a[] may be readonly */ int altsum = 0; int mina = INT_MAX; int maxa = INT_MIN; for (int i = 0; i < m; ++i) { const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0 if (mina > v) mina = v; if (maxa < v) maxa = v; altsum += pow_minus_one(v) * v; } return ((maxa-mina == m-1) and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1) - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum)); } 

En Python:

 def ispermutation(iterable, m, n): """Whether iterable and the range [n, n+m) have the same elements. pre-condition: there are no duplicates in the iterable """ for i, elem in enumerate(iterable): if not n <= elem < n+m: return False return i == m-1 print(ispermutation([1, 42], 2, 1) == False) print(ispermutation(range(10), 10, 0) == True) print(ispermutation((2, 1, 3), 3, 1) == True) print(ispermutation((2, 1, 3), 3, 0) == False) print(ispermutation((2, 1, 3), 4, 1) == False) print(ispermutation((2, 1, 3), 2, 1) == False) 

C'est O (m) dans le temps et O (1) dans l'espace. Il ne prend pas en compte les doublons.

Solution alternative:

 def ispermutation(iterable, m, n): """Same as above. pre-condition: assert(len(list(iterable)) == m) """ return all(n <= elem < n+m for elem in iterable) 

MON MEILLEUR OPTION ACTUEL

 def uniqueSet( array ) check_index = 0; check_value = 0; min = array[0]; array.each_with_index{ |value,index| check_index = check_index ^ ( 1 << index ); check_value = check_value ^ ( 1 << value ); min = value if value < min } check_index = check_index << min; return check_index == check_value; end 

O (n) et espace O (1)

J'ai écrit un script pour des combinaisons de forces brutes qui pourraient échouer et il n'en a pas trouvé. Si vous avez un tableau qui contrevient à cette fonction, dites-le. 🙂


@JF Sebastian

Ce n'est pas un véritable algorithme de hachage. Techniquement, c'est un tableau booléen emballé très efficace de valeurs "vues".

 ci = 0, cv = 0 [5,4,3]{ i = 0 v = 5 1 << 0 == 000001 1 << 5 == 100000 0 ^ 000001 = 000001 0 ^ 100000 = 100000 i = 1 v = 4 1 << 1 == 000010 1 << 4 == 010000 000001 ^ 000010 = 000011 100000 ^ 010000 = 110000 i = 2 v = 3 1 << 2 == 000100 1 << 3 == 001000 000011 ^ 000100 = 000111 110000 ^ 001000 = 111000 } min = 3 000111 << 3 == 111000 111000 === 111000 

Le fait que ceci soit principalement dû au fait que pour "simuler" la plupart des problèmes, on utilise des doublons pour le faire. Dans ce système, XOR vous pénalise d'utiliser deux fois la même valeur et suppose que vous l'avez plutôt fait 0 fois.

Les mises en garde étant bien sûr:

  1. la longueur du tableau d'entrée et la valeur maximale du tableau sont limitées par la valeur maximale de $x in ( 1 << $x > 0 )
  2. L'efficacité ultime dépend de la manière dont votre système sous-jacent met en œuvre les capacités pour:

    1. déplacez 1 bit n vers la droite.
    2. xor 2 registres. (où "registres" peuvent, selon la mise en œuvre, couvrir plusieurs registres)

    edit Noté, les déclarations ci-dessus semblent déroutantes. Assuming a perfect machine, where an "integer" is a register with Infinite precision, which can still perform a ^ b in O(1) time.

But failing these assumptions, one has to start asking the algorithmic complexity of simple math.

  • How complex is 1 == 1 ?, surely that should be O(1) every time right?.
  • What about 2^32 == 2^32 .
  • O(1)? 2^33 == 2^33? Now you've got a question of register size and the underlying implementation.
  • Fortunately XOR and == can be done in parallel, so if one assumes infinite precision and a machine designed to cope with infinite precision, it is safe to assume XOR and == take constant time regardless of their value ( because its infinite width, it will have infinite 0 padding. Obviously this doesn't exist. But also, changing 000000 to 000100 is not increasing memory usage.
  • Yet on some machines , ( 1 << 32 ) << 1 will consume more memory, but how much is uncertain.

AC version of Kent Fredric’s Ruby solution

(to facilitate testing)

Counter-example (for C version): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5, 18, 12, 2, 9, 14, 17, 21, 19, 22, 15, 20, 24, 11, 10, 16, 25}. Here n=0, m=35. This sequence misses 34 and has two 2 .

It is an O(m) in time and O(1) in space solution.

Out-of-range values are easily detected in O(n) in time and O(1) in space, therefore tests are concentrated on in-range (means all values are in the valid range [n, n+m) ) sequences. Otherwise {1, 34} is a counter example (for C version, sizeof(int)==4, standard binary representation of numbers).

The main difference between C and Ruby version: << operator will rotate values in C due to a finite sizeof(int), but in Ruby numbers will grow to accomodate the result eg,

Ruby: 1 << 100 # -> 1267650600228229401496703205376

C: int n = 100; 1 << n // -> 16

In Ruby: check_index ^= 1 << i; is equivalent to check_index.setbit(i) . The same effect could be implemented in C++: vector v(m); v[i] = true;

 bool isperm_fredric(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no ressortingction on n, ?overflow? a[] may be readonly */ int check_index = 0; int check_value = 0; int min = a[0]; for (int i = 0; i < m; ++i) { check_index ^= 1 << i; check_value ^= 1 << (a[i] - n); // if (a[i] < min) min = a[i]; } check_index <<= min - n; // min and n may differ eg, // {1, 1}: min=1, but n may be 0. return check_index == check_value; } 

Values of the above function were tested against the following code:

 bool *seen_isperm_trusted = NULL; bool isperm_trusted(int m; int a[m], int m, int n) { /** O(m) in time, O(m) in space */ for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t)); seen_isperm_trusted[i] = false; for (int i = 0; i < m; ++i) { if (a[i] < n or a[i] >= n + m) return false; // out of range if (seen_isperm_trusted[a[i]-n]) return false; // duplicates else seen_isperm_trusted[a[i]-n] = true; } return true; // a[] is a permutation of the range: [n, n+m) } 

Input arrays are generated with:

 void backtrack(int m; int a[m], int m, int nitems) { /** generate all permutations with repetition for the range [0, m) */ if (nitems == m) { (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1} } else for (int i = 0; i < m; ++i) { a[nitems] = i; backtrack(a, m, nitems + 1); } } 

The Answer from “nickf” dows not work if the array is unsorted var_dump(testArray(array(5, 3, 1, 2, 4), 1, 5)); //gives “duplicates” !!!!

Also your formula to compute sum([n…n+m-1]) looks incorrect…. the correct formula is (m(m+1)/2 – n(n-1)/2)

An array contains N numbers, and you want to determine whether two of the numbers sum to a given number K. For instance, if the input is 8,4, 1,6 and K is 10, the answer is yes (4 and 6). A number may be used twice. Procédez comme suit une. Give an O(N2) algorithm to solve this problem. b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. After doing so, you can solve the problem in linear time.) c. Code both solutions and compare the running times of your algorithms. 4.

Product of m consecutive numbers is divisible by m! [ m factorial ]


so in one pass you can compute the product of the m numbers, also compute m! and see if the product modulo m ! is zero at the end of the pass

I might be missing something but this is what comes to my mind …

something like this in python

my_list1 = [9,5,8,7,6]

my_list2 = [3,5,4,7]

def consecutive(my_list):

 count = 0 prod = fact = 1 for num in my_list: prod *= num count +=1 fact *= count if not prod % fact: return 1 else: return 0 

print consecutive(my_list1)

print consecutive(my_list2)


HotPotato ~$ python m_consecutive.py

1

0

I propose the following:

Choose a finite set of prime numbers P_1,P_2,…,P_K, and compute the occurrences of the elements in the input sequence (minus the minimum) modulo each P_i. The pattern of a valid sequence is known.

For example for a sequence of 17 elements, modulo 2 we must have the profile: [9 8], modulo 3: [6 6 5], modulo 5: [4 4 3 3 3], etc.

Combining the test using several bases we obtain a more and more precise probabilistic test. Since the ensortinges are bounded by the integer size, there exists a finite base providing an exact test. This is similar to probabilistic pseudo primality tests.

 S_i is an int array of size P_i, initially filled with 0, i=1..K M is the length of the input sequence Mn = INT_MAX Mx = INT_MIN for x in the input sequence: for i in 1..K: S_i[x % P_i]++ // count occurrences mod Pi Mn = min(Mn,x) // update min Mx = max(Mx,x) // and max if Mx-Mn != M-1: return False // Check bounds for i in 1..K: // Check profile mod P_i Q = M / P_i R = M % P_i Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1 if this test fails, return False return True 

Any contiguous array [ n, n+1, …, n+m-1 ] can be mapped on to a ‘base’ interval [ 0, 1, …, m ] using the modulo operator. For each i in the interval, there is exactly one i%m in the base interval and vice versa.

Any contiguous array also has a ‘span’ m (maximum – minimum + 1) equal to it’s size.

Using these facts, you can create an “encountered” boolean array of same size containing all falses initially, and while visiting the input array, put their related “encountered” elements to true.

This algorithm is O(n) in space, O(n) in time, and checks for duplicates.

 def contiguous( values ) #initialization encountered = Array.new( values.size, false ) min, max = nil, nil visited = 0 values.each do |v| index = v % encountered.size if( encountered[ index ] ) return "duplicates"; end encountered[ index ] = true min = v if min == nil or v < min max = v if max == nil or v > max visited += 1 end if ( max - min + 1 != values.size ) or visited != values.size return "hole" else return "contiguous" end end tests = [ [ false, [ 2,4,5,6 ] ], [ false, [ 10,11,13,14 ] ] , [ true , [ 20,21,22,23 ] ] , [ true , [ 19,20,21,22,23 ] ] , [ true , [ 20,21,22,23,24 ] ] , [ false, [ 20,21,22,23,24+5 ] ] , [ false, [ 2,2,3,4,5 ] ] ] tests.each do |t| result = contiguous( t[1] ) if( t[0] != ( result == "contiguous" ) ) puts "Failed Test : " + t[1].to_s + " returned " + result end end 

I like Greg Hewgill’s idea of Radix sorting. To find duplicates, you can sort in O(N) time given the constraints on the values in this array.

For an in-place O(1) space O(N) time that restores the original ordering of the list, you don’t have to do an actual swap on that number; you can just mark it with a flag:

 //Java: assumes all numbers in arr > 1 boolean checkArrayConsecutiveRange(int[] arr) { // find min/max int min = arr[0]; int max = arr[0] for (int i=1; i max ? arr[i] : max); } if (max-min != arr.length) return false; // flag and check boolean ret = true; for (int i=0; i 

Storing the flags inside the given array is kind of cheating, and doesn't play well with parallelization. I'm still trying to think of a way to do it without touching the array in O(N) time and O(log N) space. Checking against the sum and against the sum of least squares (arr[i] - arr.length/2.0)^2 feels like it might work. The one defining characteristic we know about a 0...m array with no duplicates is that it's uniformly dissortingbuted; we should just check that.

Now if only I could prove it.

I'd like to note that the solution above involving factorial takes O(N) space to store the factorial itself. N! > 2^N, which takes N bytes to store.

Oops! I got caught up in a duplicate question and did not see the already identical solutions here. And I thought I’d finally done something original! Here is a historical archive of when I was slightly more pleased:


Well, I have no certainty if this algorithm satisfies all conditions. In fact, I haven’t even validated that it works beyond a couple test cases I have sortinged. Even if my algorithm does have problems, hopefully my approach sparks some solutions.

This algorithm, to my knowledge, works in constant memory and scans the array three times. Perhaps an added bonus is that it works for the full range of integers, if that wasn’t part of the original problem.

I am not much of a pseudo-code person, and I really think the code might simply make more sense than words. Here is an implementation I wrote in PHP. Take heed of the comments.

 function is_permutation($ints) { /* Gather some meta-data. These scans can be done simultaneously */ $lowest = min($ints); $length = count($ints); $max_index = $length - 1; $sort_run_count = 0; /* I do not have any proof that running this sort twice will always completely sort the array (of course only intentionally happening if the array is a permutation) */ while ($sort_run_count < 2) { for ($i = 0; $i < $length; ++$i) { $dest_index = $ints[$i] - $lowest; if ($i == $dest_index) { continue; } if ($dest_index > $max_index) { return false; } if ($ints[$i] == $ints[$dest_index]) { return false; } $temp = $ints[$dest_index]; $ints[$dest_index] = $ints[$i]; $ints[$i] = $temp; } ++$sort_run_count; } return true; } 

So there is an algorithm that takes O(n^2) that does not require modifying the input array and takes constant space.

First, assume that you know n and m . This is a linear operation, so it does not add any additional complexity. Next, assume there exists one element equal to n and one element equal to n+m-1 and all the rest are in [n, n+m) . Given that, we can reduce the problem to having an array with elements in [0, m) .

Now, since we know that the elements are bounded by the size of the array, we can treat each element as a node with a single link to another element; in other words, the array describes a directed graph. In this directed graph, if there are no duplicate elements, every node belongs to a cycle, that is, a node is reachable from itself in m or less steps. If there is a duplicate element, then there exists one node that is not reachable from itself at all.

So, to detect this, you walk the entire array from start to finish and determine if each element returns to itself in <=m steps. If any element is not reachable in <=m steps, then you have a duplicate and can return false. Otherwise, when you finish visiting all elements, you can return true:

 for (int start_index= 0; start_indexm) { return false; } } return true; 

You can optimize this by storing additional information:

  1. Record sum of the length of the cycle from each element, unless the cycle visits an element before that element, call it sum_of_steps .
  2. For every element, only step m-sum_of_steps nodes out. If you don't return to the starting element and you don't visit an element before the starting element, you have found a loop containing duplicate elements and can return false .

This is still O(n^2), eg {1, 2, 3, 0, 5, 6, 7, 4} , but it's a little bit faster.

ciphwn has it right. It is all to do with statistics. What the question is asking is, in statistical terms, is whether or not the sequence of numbers form a discrete uniform dissortingbution. A discrete uniform dissortingbution is where all values of a finite set of possible values are equally probable. Fortunately there are some useful formulas to determine if a discrete set is uniform. Firstly, to determine the mean of the set (a..b) is (a+b)/2 and the variance is (nn-1)/12. Next, determine the variance of the given set:

 variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n 

and then compare with the expected variance. This will require two passes over the data, once to determine the mean and again to calculate the variance.

Les références:

  • uniform discrete dissortingbution
  • variance

Here is a solution in O(N) time and O(1) extra space for finding duplicates :-

 public static boolean check_range(int arr[],int n,int m) { for(int i=0;i=m) return(false); } System.out.println("In range"); int j=0; while(j 

Explanation:-

  1. Bring number to range (0,m-1) by arr[i] = arr[i] - n if out of range return false.
  2. for each i check if arr[arr[i]] is unoccupied that is it has value less than m
  3. if so swap(arr[i],arr[arr[i]]) and arr[arr[i]] = arr[arr[i]] + m to signal that it is occupied
  4. if arr[j] = j and simply add m and increment j
  5. if arr[arr[j]] >=m means it is occupied hence current value is duplicate hence return false.
  6. if arr[j] >= m then skip