Нахождение максимального соответствия XOR

Question

Мне нужно найти номер данной серии, которая имеет максимальное значение XOR с данным постоянным числом. Предположим так:
Данная серия: 6 7 8 9 10 и данное постоянное число равно 10. Максимальное значение XOR для 10 с другими данными числами равно 13, что для 7. Поэтому мне нужно найти 7.
Сейчас я следую стандартному подходу. Проблема в том, что когда мне дают 100000 целых чисел, мой код тратит так много времени. Есть ли другой способ выяснить это эффективно?

Answer 1

import java.util.Scanner;

public class Solution {


    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        int l = in.nextInt();
        int r = in.nextInt();

        String ls = Integer.toBinaryString(l);
        String rs = Integer.toBinaryString(r);

        if (ls.length() != rs.length()) {
            System.out.println((int)Math.pow(2, rs.length())-1);        
            return;
        }

        int len = ls.length();      
        int index=0;

        for(; index < len; ++index){
            if (ls.charAt(index) != rs.charAt(index))
                break;
        }

        if (index == len) //l = r
            System.out.println(0);
        else
            System.out.println((int)Math.pow(2, len-index)-1);
    }
}

Answer 2

Здесь можно использовать дерево.

Создайте двоичное дерево при вводе чисел с MSB вверху.

Теперь для каждого числа, например, 1011, пройдитесь по дереву за 0100 ...

В любой момент, если идеальный комплимент не найден, компромисс для того, что доступно, продолжайте.

Answer 3

Пусть a - это массив, а q - это число.

Сначала вы сортируете указанный массив, а затем выполняете двоичный поиск для (MAX-q), где MAX - максимально возможное целое число (2 * +1007 * 31 -1).Идея состоит в том, что значение exor является максимальным, когда все биты противоположны битам в числе q.

Answer 4

int L = 0, R = n-1;
for(int i = 31; i >= 0 && L < R; i--) {
  if(((a[L]>>i)&1) == ((a[R]>>i)&1))
    continue;
  int l = L, r = R;
  while(r - l > 1) {
    int m = (r+l)/2;
    if((a[m]>>i)&1) r = m;
    else l = m;
  }
  if((b>>i)&1) R = l;
  else L = r;
}

L - индекс числа, которое максимизирует xor с номером b, в то время как a содержит номер в отсортированном порядке

Answer 5

Самый быстрый способ, который я могу придумать, - это циклически перебирать ваш массив чисел и делать XOR их с вашей константой, находя максимальное значение по мере того, как вы идете, сравнивая их с наибольшим из найденных вами ранее.После нахождения наибольшего числа просто введите XOR с вашей константой снова, чтобы найти исходное значение.

Код Java:

public int findMaximumXOR(int[] nums, int constantNum)
{
    int largest = nums[0] ^ constantNum;
    for (int i = 1; i<nums.length; ++i)
        if (largest<(nums[i] ^ constantNum))
            largest = (nums[i] ^ constantNum);

    return (largest ^ constantNum);
}