Рубрики

Минимальная пара значений XOR

Дан массив целых чисел. Найдите пару в массиве с минимальным значением XOR.
Примеры :

Input : arr[] =  {9, 5, 3}
Output : 6
        All pair with xor value (9 ^ 5) => 12, 
        (5 ^ 3) => 6, (9 ^ 3) => 10.
        Minimum XOR value is 6

Input : arr[] = {1, 2, 3, 4, 5}
Output : 1 

Простое решение — сгенерировать все пары заданного массива и вычислить XOR их значения. Наконец, вернуть минимальное значение XOR. Это решение занимает O (n 2 ) время.

C ++

// C ++ программа для поиска минимального значения XOR в массиве.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает минимальное значение xor пары в arr [0..n-1]

int minXOR(int arr[], int n)

{

    int min_xor = INT_MAX; // Инициализировать результат

  

    // Генерируем все пары данного массива

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

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

  

            // обновляем минимальное значение xor, если требуется

            min_xor = min(min_xor, arr[i] ^ arr[j]);

  

    return min_xor;

}

  
// Драйвер программы

int main()

{

    int arr[] = { 9, 5, 3 };

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

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

    return 0;

}

Джава

// Java программа для поиска минимального значения XOR в массиве.

class GFG {

  

    // Возвращает минимальное значение xor пары в arr [0..n-1]

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

    {

        int min_xor = Integer.MAX_VALUE; // Инициализировать результат

  

        // Генерируем все пары данного массива

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

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

  

                // обновляем минимальное значение xor, если требуется

                min_xor = Math.min(min_xor, arr[i] ^ arr[j]);

  

        return min_xor;

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        int arr[] = { 9, 5, 3 };

        int n = arr.length;

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

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Python программа для поиска минимума
# Значение XOR в массиве.

  
# Функция для поиска минимальной пары XOR

def minXOR(arr, n):

      

    # Сортировать данный массив

    arr.sort();

  

    min_xor = 999999

    val = 0

  

    # рассчитать мин xor из

    # последовательных пар

    for i in range (0, n-1):

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

              

            # обновить минимальное значение xor

            # если необходимо

            val = arr[i] ^ arr[j]

            min_xor = min(min_xor, val)

    return min_xor

  
# Драйверная программа

arr = [ 9, 5, 3 ]

n = len(arr)

  

print(minXOR(arr, n))

  
# Этот код предоставлен Sam007.

C #

// C # программа для поиска минимума
// значение XOR в массиве.

using System;

  

class GFG {

      

    // Возвращает минимальное значение xor

    // пара в обр [0..n-1]

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

    {

         // Инициализировать результат

        int min_xor = int.MaxValue;

  

        // Генерируем все пары данного массива

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

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

  

            // обновляем минимальное значение xor, если требуется

            min_xor = Math.Min(min_xor, arr[i] ^ arr[j]);

  

        return min_xor;

    }

  

    // Драйвер программы

    public static void Main()

    {

        int[] arr = { 9, 5, 3 };

        int n = arr.Length;

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

    }

}

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

PHP

<?php
// PHP программа для поиска минимума
// значение XOR в массиве.

  
// Возвращает минимальное значение xor
// пары в arr [0..n-1]

function minXOR($arr, $n)

{

    // Инициализировать результат

    $min_xor = PHP_INT_MAX; 

  

    // Генерируем все пары данного массива

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

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

  

            // обновляем минимальное значение xor

            // значение, если требуется

            $min_xor = min($min_xor, $arr[$i] ^ $arr[$j]);

  

    return $min_xor;

}

  

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

    $arr = array(9, 5, 3);

    $n = count($arr);

    echo minXOR($arr, $n);

      
// Этот код предоставлен anuj_67.
?>


Выход :

6

Эффективное решение может решить эту проблему в течение O (nlogn) времени. Ниже приведен алгоритм:

1). Sort the given array
2). Traverse and check XOR for every consecutive pair

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

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска минимальной пары XOR

int minXOR(int arr[], int n)

{

    // Сортировать указанный массив

    sort(arr, arr + n);

  

    int minXor = INT_MAX;

    int val = 0;

  

    // вычисляем минимум xor последовательных пар

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

        val = arr[i] ^ arr[i + 1];

        minXor = min(minXor, val);

    }

  

    return minXor;

}

  
// Драйвер программы

int main()

{

    int arr[] = { 9, 5, 3 };

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

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

  

    return 0;

}

Джава

import java.util.Arrays;

class GFG {

  

    // Функция для поиска минимальной пары XOR

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

    {

        // Сортировать указанный массив

        Arrays.parallelSort(arr);

  

        int minXor = Integer.MAX_VALUE;

        int val = 0;

  

        // вычисляем минимум xor последовательных пар

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

            val = arr[i] ^ arr[i + 1];

            minXor = Math.min(minXor, val);

        }

  

        return minXor;

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        int arr[] = { 9, 5, 3 };

        int n = arr.length;

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

    }

}

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

python3

  import sys    

  
# Функция для поиска минимальной пары XOR

def minXOR(arr, n):

      

    # Сортировать данный массив

    arr.sort()

   

    minXor =  int(sys.float_info.max)

    val = 0

   

    # рассчитать мин xor последовательных пар

    for i in range(0,n-1):

        val = arr[i] ^ arr[i + 1];

        minXor = min(minXor, val);

      

    return minXor

  
# Драйверная программа

arr = [9, 5, 3]

n = len(arr)

print(minXOR(arr, n))

   
# Этот код предоставлен Sam007.

C #

// C # программа для поиска минимума
// значение XOR в массиве.

using System;

  

class GFG {

      

    // Функция для поиска минимальной пары XOR

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

    {

        // Сортировать указанный массив

        Array.Sort(arr);

  

        int minXor = int.MaxValue;

        int val = 0;

  

        // вычисляем минимум xor последовательных пар

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

            val = arr[i] ^ arr[i + 1];

            minXor = Math.Min(minXor, val);

        }

  

        return minXor;

    }

  

    // Драйвер программы

    public static void Main()

    {

        int[] arr = { 9, 5, 3 };

        int n = arr.Length;

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

    }

}

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

PHP

<?php
// Функция для поиска минимальной пары XOR

function minXOR($arr, $n)

{

    // Сортировать указанный массив

    sort($arr);

  

    $minXor = PHP_INT_MAX;

    $val = 0;

  

    // вычисляем мин xor

    // последовательных пар

    for ($i = 0; $i < $n - 1; $i++) 

    {

        $val = $arr[$i] ^ $arr[$i + 1];

        $minXor = min($minXor, $val);

    }

  

    return $minXor;

}

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

$arr = array(9, 5, 3);

$n = count($arr);

echo minXOR($arr, $n);

  
// Этот код предоставлен Smitha.
?>

Выход :

6

Сложность времени: O (N * logN)
Космическая сложность: O (1)
Спасибо Уткаршу Гупте за предложенный выше подход.
Еще одно более эффективное решение может решить вышеуказанную проблему за O (n) время в предположении, что целые числа сохраняют фиксированное количество битов. Идея состоит в том, чтобы использовать структуру данных Trie. Ниже приведен алгоритм.

1). Create an empty trie. Every node of trie contains two children
    for 0 and 1 bits.
2). Initialize min_xor = INT_MAX, insert arr[0] into trie
3). Traversal all array element one-by-one starting from second.
     a. First find minimum setbet difference value in trie 
        do xor of current element with minimum setbit diff that value 
     b. update min_xor value if required
     c. insert current array element in trie 
4). return min_xor
  

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

C ++

// C ++ программа для поиска минимального значения XOR в массиве.
#include <bits/stdc++.h>

using namespace std;

#define INT_SIZE 32

  
// Узел Trie

struct TrieNode {

    int value; // используется в листовом узле

    TrieNode* Child[2];

};

  
// Сервисная функция для создания нового узла Trie
TrieNode* getNode()
{

    TrieNode* newNode = new TrieNode;

    newNode->value = 0;

    newNode->Child[0] = newNode->Child[1] = NULL;

    return newNode;

}

  
// служебная функция вставляет новый ключ в три

void insert(TrieNode* root, int key)

{

    TrieNode* temp = root;

  

    // начинаем с самого старшего бита, вставляем все

    // бит ключа один за другим в три

    for (int i = INT_SIZE - 1; i >= 0; i--) {

        // Найти текущий бит в заданном префиксе

        bool current_bit = (key & (1 << i));

  

        // Добавить новый узел в три

        if (temp->Child[current_bit] == NULL)

            temp->Child[current_bit] = getNode();

  

        temp = temp->Child[current_bit];

    }

  

    // сохранить значение на leafNode

    temp->value = key;

}

  
// Возвращает минимальное значение XOR вставленного целого числа
// в Trie и указан ключ.

int minXORUtil(TrieNode* root, int key)

{

    TrieNode* temp = root;

  

    for (int i = INT_SIZE - 1; i >= 0; i--) {

        // Найти текущий бит в заданном префиксе

        bool current_bit = (key & (1 << i));

  

        // Обход Три, ищем префикс, который имеет

        // тот же бит

        if (temp->Child[current_bit] != NULL)

            temp = temp->Child[current_bit];

  

        // если нет такого же бита, то ищем

        // противоположный бит

        else if (temp->Child[1 - current_bit] != NULL)

            temp = temp->Child[1 - current_bit];

    }

  

    // возвращаем значение xor минимального значения битовой разности

    // поэтому мы получаем минимальное значение xor

    return key ^ temp->value;

}

  
// Возвращает минимальное значение xor пары в arr [0..n-1]

int minXOR(int arr[], int n)

{

    int min_xor = INT_MAX; // Инициализировать результат

  

    // создаем True и вставляем в него первый элемент

    TrieNode* root = getNode();

    insert(root, arr[0]);

  

    // Обходим весь элемент массива и находим минимальное значение xor

    // для каждого элемента

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

        // Находим минимальное значение XOR текущего элемента с

        // предыдущие элементы вставлены в Trie

        min_xor = min(min_xor, minXORUtil(root, arr[i]));

  

        // вставить текущее значение массива в Trie

        insert(root, arr[i]);

    }

    return min_xor;

}

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

int main()

{

    int arr[] = { 9, 5, 3 };

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

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

    return 0;

}

Джава

// Java программа для поиска минимального значения XOR в массиве.

class GFG {

    static final int INT_SIZE = 32;

  

    // Узел Trie

    static class TrieNode {

        int value; // используется в листовом узле

        TrieNode[] Child = new TrieNode[2];

  

        public TrieNode()

        {

            value = 0;

            Child[0] = null;

            Child[1] = null;

        }

    }

    static TrieNode root;

  

    // служебная функция вставляет новый ключ в три

    static void insert(int key)

    {

        TrieNode temp = root;

  

        // начинаем с самого старшего бита, вставляем все

        // бит ключа один за другим в три

        for (int i = INT_SIZE - 1; i >= 0; i--) {

            // Найти текущий бит в заданном префиксе

            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;

  

            // Добавить новый узел в три

            if (temp != null && temp.Child[current_bit] == null)

                temp.Child[current_bit] = new TrieNode();

  

            temp = temp.Child[current_bit];

        }

  

        // сохранить значение на leafNode

        temp.value = key;

    }

  

    // Возвращает минимальное значение XOR вставленного целого числа

    // в Trie и указан ключ.

    static int minXORUtil(int key)

    {

        TrieNode temp = root;

  

        for (int i = INT_SIZE - 1; i >= 0; i--) {

            // Найти текущий бит в заданном префиксе

            int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;

  

            // Обход Три, ищем префикс, который имеет

            // тот же бит

            if (temp.Child[current_bit] != null)

                temp = temp.Child[current_bit];

  

            // если нет такого же бита, то ищем

            // противоположный бит

            else if (temp.Child[1 - current_bit] != null)

                temp = temp.Child[1 - current_bit];

        }

  

        // возвращаем значение xor минимального значения битовой разности

        // поэтому мы получаем минимальное значение xor

        return key ^ temp.value;

    }

  

    // Возвращает минимальное значение xor пары в arr [0..n-1]

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

    {

        int min_xor = Integer.MAX_VALUE; // Инициализировать результат

  

        // создаем True и вставляем в него первый элемент

        root = new TrieNode();

        insert(arr[0]);

  

        // Обходим весь элемент массива и находим минимальное значение xor

        // для каждого элемента

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

            // Находим минимальное значение XOR текущего элемента с

            // предыдущие элементы вставлены в Trie

            min_xor = Math.min(min_xor, minXORUtil(arr[i]));

  

            // вставить текущее значение массива в Trie

            insert(arr[i]);

        }

        return min_xor;

    }

  

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

    public static void main(String args[])

    {

        int arr[] = { 9, 5, 3 };

        int n = arr.length;

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

    }

}
// Этот код предоставлен Sumit Ghosh

Выход :

6

Сложность времени O (n)

Эта статья предоставлена Nishant_Singh (Pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Минимальная пара значений XOR

0.00 (0%) 0 votes