Deux éléments dans un tableau dont le xor est maximum

Question

Étant donné un tableau d'entiers, vous devez trouver deux éléments dont le XOR est maximum.

Il y a une approche naïve - il suffit de choisir chaque élément, puis d’en analyser d’autres, puis de comparer les résultats pour trouver la paire.

En dehors de cela, existe-t-il un algorithme efficace?

Answer 1

Je pense que j'ai un temps O(n lg U) algorithme pour cela, où U est le plus grand nombre. L'idée est semblable à user949300, mais avec un peu plus de détail.

L'intuition est comme suit. Lorsque vous êtes XORing deux nombres ensemble, pour obtenir le maximum de valeur, vous voulez avoir un 1 à la position la plus élevée possible, puis de les appariements qui ont un 1 à ce poste, vous voulez une liaison avec un 1 à la prochaine position la plus haute, etc.

Donc, l'algorithme est le suivant. Commencer par trouver plus de 1 peu partout dans les numéros (vous pouvez le faire en temps O(n lg U) en faisant O(lg U) par chacun des n nombres). Maintenant, de diviser le tableau en deux parties - l'un des numéros qui ont un 1 dans le peu et le groupe avec 0 dans le peu. Toute solution optimale doit combiner un nombre avec un 1 dans la première place avec un nombre de 0 dans cet endroit, parce que ce serait mettre un bit à 1 aussi haut que possible. Toute autre couplage a un 0 de là.

Maintenant, de manière récursive, nous voulons trouver le couplage de nombres à partir de 1 et 0 dans le groupe qui a le plus grand 1 en eux. Pour ce faire, de ces deux groupes, les diviser en quatre groupes:

• Les numéros commençant par 11
• Les numéros commençant par 10
• Les numéros commençant par 01
• Les numéros commençant par 00

S'il y a des chiffres dans le 11 et 00 groupe ou dans le 10 et 01 groupes, leur XOR serait l'idéal (à partir de 11). Par conséquent, si l'une de ces paires de groupes n'est pas vide, de façon récursive de calcul la solution idéale pour les groupes, puis retourner le maximum de ces subproblem solutions. Sinon, si les deux groupes sont vides, ce qui signifie que tous les chiffres doivent avoir le même chiffre dans leur deuxième position. Par conséquent, la meilleure XOR d'un numéro 1 et un numéro commençant par 0 finalement la seconde suivante bits annuler, nous devrions donc il suffit de regarder la troisième bit.

Cela donne à la suite algorithme récursif qui, commençant avec les deux groupes de chiffres séparées par leur MSB, donne la réponse:

• Groupe 1 et le groupe 0 et un peu d'indice i:
  • Si le bit d'indice est égal au nombre de bits, le retour de la XOR de l' (unique) dans le 1er groupe et le (unique) dans le groupe 0.
  • Construire des groupes de 11, 10, 01, 00 et à partir de ces groupes.
  • Si le groupe 11 groupe et 00 sont non vides, de manière récursive trouver le maximum d'XOR de ces deux groupes au départ de bit i + 1.
  • Si le groupe 10 et du groupe 01 sont non vides, de manière récursive trouver le maximum d'XOR de ces deux groupes, en commençant à peu, j'ai + 1.
  • Si une de ces paires a été possible, puis retourner le maximum de pair par la récursivité.
  • Sinon, tous les chiffres doivent avoir le même bit à la position i, afin de renvoyer le maximum de paires trouvé en cherchant un peu j' + 1 sur les groupes 1 et 0.

Pour commencer l'algorithme, vous pouvez en fait juste la partition de l'un des numéros du groupe initial en deux groupes - les numéros avec l'ESM 1 et des nombres avec le MSB 0. Vous alors de déclencher un appel récursif de l'algorithme ci-dessus avec les deux groupes de nombres.

Considérez, par exemple, les numéros 5 1 4 3 0 2. Ces représentations ont

101  001  100   011   000   010

Nous commençons par découper dans le 1 et le 0 groupe:

101  100
001  011  000  010

Maintenant, nous appliquons l'algorithme ci-dessus. Nous nous sommes répartis en groupes de 11, 10, 01, et 00:

11:
10:  101  100
01:  011  010
00:  000  001

Maintenant, nous ne pouvons pas paire tout de 11 éléments, avec 00 éléments, afin que nous venons de manière récursive sur les 10 et 01 groupes. Cela signifie que nous avons de construire 100, 101, 010 et 011 groupes:

101: 101
100: 100
011: 011
010: 010

Maintenant que nous en sommes à seaux avec juste un élément en eux, il nous suffit de vérifier les paires 101 et 010 (qui donne 111) et 100 011 (qui donne 111). L'option fonctionne ici, nous obtenons donc, la meilleure réponse est 7.

Nous allons réfléchir sur le temps d'exécution de cet algorithme. Notez que le maximum de la profondeur de récursion est O(lg U), il n'y a que O(log U) bits dans les chiffres. À chaque niveau de l'arborescence, chaque numéro s'affiche dans exactement un appel récursif, et chacun des appels récursifs ne fonctionne proportionnelle au nombre total de nombres 0 et 1 groupes, parce que nous avons besoin de les distribuer par leurs bits. Par conséquent, il y a O(log U) les niveaux de la récursivité de l'arbre, et chaque niveau ne O(n) de travail, ce qui donne un total de travail de O(n log U).

Espérons que cette aide! Ce était un jeu génial de problème!

Answer 2

Ignorant le bit de signe, l'une des valeurs doit être l'une des valeurs les plus importantes ensemble de bits. À moins que toutes les valeurs ont que peu ensemble, dans ce cas, vous allez à la prochaine plus haute de bits significatifs qui n'est pas défini dans toutes les valeurs. Donc, vous pourriez réduire les possibilités pour la 1ère valeur en regardant le TSL. Par exemple, si les possibilités sont

0x100000
0x100ABC
0x001ABC
0x000ABC

La 1ère valeur de la max la paire doit être 0x100000 ou 0x10ABCD.

@Erreur interne du Serveur, je ne pense pas que la plus petite est nécessairement correcte. Je n'ai pas une grande idée pour éplucher la 2ème valeur. Juste une valeur qui n'est pas dans la liste des possibles 1er valeurs. Dans mon exemple, 0x001ABC ou 0x000ABC.

Answer 3

Une très intéressante problème! Voici mon idée:

• D'abord construire un arbre binaire de tous les nombres en utilisant les binaires de représentation et de les trier dans l'arbre bit de poids fort en premier (ajouter des zéros non significatifs pour le match le plus long nombre). Lorsque terminé, chaque chemin à partir de la racine de toute la feuille représente un nombre à partir de l'original ensemble.
• Soient a et b des pointeurs vers un nœud de l'arborescence et de les initialiser à la racine.
• Maintenant aller de a et b en bas de l'arbre, essayez d'utiliser des arêtes opposées à chaque étape, c'est à dire si se déplace vers le bas d'un 0-bord, b se déplace vers le bas d'un 1-bord, à moins que ce n'est pas possible.

Si a et b atteignent une feuille, le doit pointer vers deux numéros avec "très peu" à l'identique bits.

Je viens de faire cet algorithme et de ne pas savoir s'il est correct ou la façon de le prouver. Cependant, il devrait être en O(n) temps de fonctionnement.

Answer 4

Faire une fonction récursive qui prend deux listes d'entiers A et B, comme ses arguments. Comme sa valeur de retour, il retourne deux entiers, l'un de A et de B, qui maximisent le XOR de deux. Si tous les entiers de 0, de retour de (0,0). Sinon, la fonction fait un peu de traitement et appelle récursivement deux fois, mais avec de plus petits nombres entiers. Dans l'un des appels récursifs, il considère que la prise d'un nombre entier à partir d'Une liste pour la fourniture de 1 à k bits, et dans l'autre appel il envisage de prendre un nombre entier à partir de la liste B pour la fourniture de 1 à k bits.

Je n'ai pas le temps maintenant de remplir les détails, mais peut-être que ce sera assez pour voir la réponse? Aussi, je ne suis pas sûr si le temps d'exécution sera meilleure que les N^2, mais il sera probablement.