Рубрики

Максимальное XOR двух чисел в массиве

Дан массив Arr неотрицательных целых чисел размера N. Задача состоит в том, чтобы найти максимально возможное значение xor между двумя числами, присутствующими в массиве.

Пример :

Input: Arr = {25, 10, 2, 8, 5, 3}
Output: 28
The maximum result is 5 ^ 25 = 28

Input: Arr = {1, 2, 3, 4, 5, 6, 7}
Output: 7
The maximum result is 1 ^ 6 = 7

Наивный подход: простое решение состоит в том, чтобы сгенерировать все пары данного массива и вычислить XOR пар. Наконец, верните максимальное значение XOR. Это решение требует время.

Ниже приведена реализация вышеуказанного подхода:

C ++

// реализация C ++
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата
// максимальный xor

int max_xor(int arr[], int n)

{

  

    int maxXor = 0;

  

    // Вычисление xor каждой пары

    for (int i = 0; i < n; i++) {

        for (int j = i + 1; j < n; j++) {

            maxXor = max(maxXor,

                         arr[i] ^ arr[j]);

        }

    }

    return maxXor;

}

  
// Код драйвера

int main()

{

  

    int arr[] = { 25, 10, 2, 8, 5, 3 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << max_xor(arr, n) << endl;

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  

    // Функция для возврата

    // максимальный xor

    static int max_xor(int arr[], int n) 

    {

        int maxXor = 0;

  

        // Вычисление xor каждой пары

        for (int i = 0; i < n; i++)

        {

            for (int j = i + 1; j < n; j++) 

            {

                maxXor = Math.max(maxXor,

                        arr[i] ^ arr[j]);

            }

        }

        return maxXor;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int arr[] = {25, 10, 2, 8, 5, 3};

        int n = arr.length;

  

        System.out.println(max_xor(arr, n));

    }

  
// Этот код предоставлен Rajput-Ji

python3

# Реализация Python3

  
# Функция для возврата
# максимальное значение xor

def max_xor(arr, n):

  

    maxXor = 0;

  

    # Расчет xor каждой пары

    for i in range(n):

        for j in range(i + 1, n):

            maxXor = max(maxXor,\

                         arr[i] ^ arr[j]);

  

    return maxXor;

  
Код водителя

if __name__ == '__main__':

  

    arr = [ 25, 10, 2, 8, 5, 3 ];

    n = len(arr);

  

    print(max_xor(arr, n));

  
# Этот код предоставлен 29AjayKumar

C #

// C # реализация подхода

using System;

  

class GFG 

{

  
// Функция для возврата
// максимальный xor

static int max_xor(int []arr, int n) 

{

    int maxXor = 0;

  

    // Вычисление xor каждой пары

    for (int i = 0; i < n; i++)

    {

        for (int j = i + 1; j < n; j++) 

        {

            maxXor = Math.Max(maxXor,

                              arr[i] ^ arr[j]);

        }

    }

    return maxXor;

}

  
// Код драйвера

public static void Main() 

{

    int []arr = {25, 10, 2, 8, 5, 3};

    int n = arr.Length;

  

    Console.WriteLine(max_xor(arr, n));

}
}

  
// Этот код предоставлен AnkitRai01

Выход:

28

Сложность времени: где N — размер массива

Эффективный подход: подход аналогичен этой статье, где задача состоит в том, чтобы найти пару максимального значения .
Таким образом, идея состоит в том, чтобы изменить постановку задачи с поиска максимального значения xor двух чисел в массиве, чтобы -> найти два числа в массиве, так что значение xor равно числу X. В этом случае X будет максимальным числом, которого мы хотим достичь до i-го бита.

Чтобы найти наибольшее значение операции XOR, значение xor должно иметь каждый бит, который должен быть установленным битом, т. Е. 1. В 32-битном числе цель состоит в том, чтобы получить максимально 1 набор, начиная слева направо.

Для оценки каждого бита для этого бита требуется маска . Маска определяет, какой бит должен присутствовать в ответе, а какой нет. Здесь мы будем использовать маску, чтобы сохранить префикс для каждого числа (то есть, взяв ответ с маской, сколько бит осталось от числа) на входе до i-го бита, затем со списком возможных чисел в нашем наборе, после вставки числа мы оценим, сможем ли мы обновить максимум для этой позиции бита до 1.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата
// максимальный xor

int max_xor(int arr[], int n)

{

    int maxx = 0, mask = 0;

  

    set<int> se;

  

    for (int i = 30; i >= 0; i--) {

  

        // устанавливаем i-й бит в маску

        // как 100000, 110000, 111000 ..

        mask |= (1 << i);

  

        for (int i = 0; i < n; ++i) {

  

            // Просто сохраняем префикс до

            // я немного пренебрегаю всем

            // бит после того как я

            se.insert(arr[i] & mask);

        }

  

        int newMaxx = maxx | (1 << i);

  

        for (int prefix : se) {

  

            // найти две пары в наборе

            // такой, что a ^ b = newMaxx

            // который является самым высоким

            // возможный бит может быть получен

            if (se.count(newMaxx ^ prefix)) {

                maxx = newMaxx;

                break;

            }

        }

  

        // очистить набор для следующего

        // итерация

        se.clear();

    }

  

    return maxx;

}

  
// Код драйвера

int main()

{

  

    int arr[] = { 25, 10, 2, 8, 5, 3 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << max_xor(arr, n) << endl;

  

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

import java.util.*;

class GFG

{

  
// Функция для возврата
// максимальный xor

static int max_xor(int arr[], int n)

{

    int maxx = 0, mask = 0;

  

    HashSet<Integer> se = new HashSet<Integer>();

  

    for (int i = 30; i >= 0; i--) 

    {

  

        // устанавливаем i-й бит в маску

        // как 100000, 110000, 111000 ..

        mask |= (1 << i);

  

        for (int j = 0; j < n; ++j) 

        {

  

            // Просто сохраняем префикс до

            // я немного пренебрегаю всем

            // бит после того как я

            se.add(arr[j] & mask);

        }

  

        int newMaxx = maxx | (1 << i);

  

        for (int prefix : se)

        {

  

            // найти две пары в наборе

            // такой, что a ^ b = newMaxx

            // который является самым высоким

            // возможный бит может быть получен

            if (se.contains(newMaxx ^ prefix))

            {

                maxx = newMaxx;

                break;

            }

        }

  

        // очистить набор для следующего

        // итерация

        se.clear();

    }

    return maxx;

}

  
// Код драйвера

public static void main(String[] args)

{

    int arr[] = { 25, 10, 2, 8, 5, 3 };

    int n = arr.length;

  

    System.out.println(max_xor(arr, n));

}

  
// Этот код предоставлен Rajput-Ji

C #

// C # реализация вышеуказанного подхода

using System;

using System.Collections.Generic;

      

class GFG

{

  
// Функция для возврата
// максимальный xor

static int max_xor(int []arr, int n)

{

    int maxx = 0, mask = 0;

  

    HashSet<int> se = new HashSet<int>();

  

    for (int i = 30; i >= 0; i--) 

    {

  

        // устанавливаем i-й бит в маску

        // как 100000, 110000, 111000 ..

        mask |= (1 << i);

  

        for (int j = 0; j < n; ++j) 

        {

  

            // Просто сохраняем префикс до

            // я немного пренебрегаю всем

            // бит после того как я

            se.Add(arr[j] & mask);

        }

  

        int newMaxx = maxx | (1 << i);

  

        foreach (int prefix in se)

        {

  

            // найти две пары в наборе

            // такой, что a ^ b = newMaxx

            // который является самым высоким

            // возможный бит может быть получен

            if (se.Contains(newMaxx ^ prefix))

            {

                maxx = newMaxx;

                break;

            }

        }

  

        // очистить набор для следующего

        // итерация

        se.Clear();

    }

    return maxx;

}

  
// Код драйвера

public static void Main(String[] args)

{

    int []arr = { 25, 10, 2, 8, 5, 3 };

    int n = arr.Length;

  

    Console.WriteLine(max_xor(arr, n));

}
}

  
// Этот код предоставлен Принчи Сингхом

Выход:

28

Сложность времени: где N — размер массива, а M — максимальное число, присутствующее в массиве.

Рекомендуемые посты:

Максимальное XOR двух чисел в массиве

0.00 (0%) 0 votes