Найдите такое число, чтобы максимум в массиве был минимально возможным после XOR

Опубликовано: 5 Января, 2022

Дан массив неотрицательных целых чисел. Выберите целое число P и выполните XOR P со всеми элементами массива. Задача состоит в том, чтобы выбрать P так, чтобы максимальное значение массива было минимально возможным после выполнения XOR всех элементов массива с P.

Примеры:

Input: arr = {3, 2, 1} 
Output:
Explanation: 
We can choose P = 3 such that after taking XOR the maximum element is minimum possible. 
After taking exclusive-OR arr = {0, 1, 2} 
2 is minimum possible value.
Input: arr = {5, 1} 
Output: 4

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  • Мы можем решить эту проблему рекурсивно, начиная со старшего бита.
  • Разделите элементы на две группы: одна с элементами, у которых текущий бит включен (1), а другая с элементами, у которых текущий бит выключен (0).
  • Если какая-либо группа пуста, мы можем назначить текущий бит P соответственно, чтобы у нас был отключен текущий бит в нашем ответе.
  • В противном случае, если обе группы не пусты, поэтому какое бы значение мы ни присвоили текущему биту P, в нашем ответе этот бит будет на (1).
  • Теперь, чтобы решить, какое значение присвоить текущему биту P, мы рекурсивно вызовем для каждой из групп следующий бит и вернем минимум обоих.

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

C ++

// C++ program that find the minimum
// possible maximum
#include <bits/stdc++.h>
using namespace std;
// Recursive function that find the
// minimum value after exclusive-OR
int RecursiveFunction(vector< int > ref,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.size() == 0 || bit < 0)
return 0;
vector< int > curr_on, curr_off;
for ( int i = 0; i < ref.size(); i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref[i] >> bit) & 1) == 0)
curr_off.push_back(ref[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.push_back(ref[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.size() == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.size() == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1))
+ (1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
void PrintMinimum( int a[], int n)
{
vector< int > v;
// Pushing values in vector
for ( int i = 0; i < n; i++)
v.push_back(a[i]);
// Printing answer
cout << RecursiveFunction(v, 30)
<< " " ;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1 };
int size = sizeof (arr) / sizeof (arr[0]);
PrintMinimum(arr, size);
return 0;
}

Джава

// Java program that find the minimum
// possible maximum
import java.util.*;
class GFG{
// Recursive function that find the
// minimum value after exclusive-OR
static int RecursiveFunction(ArrayList<Integer> ref,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.size() == 0 || bit < 0 )
return 0 ;
ArrayList<Integer> curr_on = new ArrayList<>();
ArrayList<Integer> curr_off = new ArrayList<>();
for ( int i = 0 ; i < ref.size(); i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref.get(i) >> bit) & 1 ) == 0 )
curr_off.add(ref.get(i));
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.add(ref.get(i));
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.size() == 0 )
return RecursiveFunction(curr_on, bit - 1 );
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.size() == 0 )
return RecursiveFunction(curr_off, bit - 1 );
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.min(RecursiveFunction(curr_off,
bit - 1 ),
RecursiveFunction(curr_on,
bit - 1 )) +
( 1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
static void PrintMinimum( int a[], int n)
{
ArrayList<Integer> v = new ArrayList<>();
// Pushing values in vector
for ( int i = 0 ; i < n; i++)
v.add(a[i]);
// Printing answer
System.out.println(RecursiveFunction(v, 30 ));
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3 , 2 , 1 };
int size = arr.length;
PrintMinimum(arr, size);
}
}
// This code is contributed by jrishabh99

Python3

# Python3 program that find
# the minimum possible maximum
# Recursive function that find the
# minimum value after exclusive-OR
def RecursiveFunction(ref, bit):
# Condition if ref size is zero or
# bit is negative then return 0
if ( len (ref) = = 0 or bit < 0 ):
return 0 ;
curr_on = []
curr_off = []
for i in range ( len (ref)):
# Condition if current bit is
# off then push current value
# in curr_off vector
if (((ref[i] >> bit) & 1 ) = = 0 ):
curr_off.append(ref[i])
# Condition if current bit is on
# then push current value in
# curr_on vector
else :
curr_on.append(ref[i])
# Condition if curr_off is empty
# then call recursive function
# on curr_on vector
if ( len (curr_off) = = 0 ):
return RecursiveFunction(curr_on,
bit - 1 )
# Condition if curr_on is empty
# then call recursive function
# on curr_off vector
if ( len (curr_on) = = 0 ):
return RecursiveFunction(curr_off,
bit - 1 )
# Return the minimum of curr_off and
# curr_on and add power of 2 of
# current bit
return ( min (RecursiveFunction(curr_off,
bit - 1 ),
RecursiveFunction(curr_on,
bit - 1 )) + ( 1 << bit))
# Function that print the minimum
# value after exclusive-OR
def PrintMinimum(a, n):
v = []
# Pushing values in vector
for i in range (n):
v.append(a[i])
# Printing answer
print (RecursiveFunction(v, 30 ))
# Driver Code
arr = [ 3 , 2 , 1 ]
size = len (arr)
PrintMinimum(arr, size)
#This code is contributed by avanitrachhadiya2155

C #

// C# program that find the minimum
// possible maximum
using System;
using System.Collections.Generic;
class GFG{
// Recursive function that find the
// minimum value after exclusive-OR
static int RecursiveFunction(List< int > re,
int bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (re.Count == 0 || bit < 0)
return 0;
List< int > curr_on = new List< int >();
List< int > curr_off = new List< int >();
for ( int i = 0; i < re.Count; i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((re[i] >> bit) & 1) == 0)
curr_off.Add(re[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.Add(re[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.Count == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.Count == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.Min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1)) +
(1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
static void PrintMinimum( int []a, int n)
{
List< int > v = new List< int >();
// Pushing values in vector
for ( int i = 0; i < n; i++)
v.Add(a[i]);
// Printing answer
Console.WriteLine(RecursiveFunction(v, 30));
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1 };
int size = arr.Length;
PrintMinimum(arr, size);
}
}
// This code is contributed by Amit Katiyar

Javascript

<script>
// Javascript program that find the minimum
// possible maximum
// Recursive function that find the
// minimum value after exclusive-OR
function RecursiveFunction(ref, bit)
{
// Condition if ref size is zero or
// bit is negative then return 0
if (ref.length == 0 || bit < 0)
return 0;
let curr_on = [], curr_off = [];
for (let i = 0; i < ref.length; i++)
{
// Condition if current bit is
// off then push current value
// in curr_off vector
if (((ref[i] >> bit) & 1) == 0)
curr_off.push(ref[i]);
// Condition if current bit is on
// then push current value in
// curr_on vector
else
curr_on.push(ref[i]);
}
// Condition if curr_off is empty
// then call recursive function
// on curr_on vector
if (curr_off.length == 0)
return RecursiveFunction(curr_on,
bit - 1);
// Condition if curr_on is empty
// then call recursive function
// on curr_off vector
if (curr_on.length == 0)
return RecursiveFunction(curr_off,
bit - 1);
// Return the minimum of curr_off and
// curr_on and add power of 2 of
// current bit
return Math.min(RecursiveFunction(curr_off,
bit - 1),
RecursiveFunction(curr_on,
bit - 1))
+ (1 << bit);
}
// Function that print the minimum
// value after exclusive-OR
function PrintMinimum(a, n)
{
let v = [];
// Pushing values in vector
for (let i = 0; i < n; i++)
v.push(a[i]);
// Printing answer
document.write(RecursiveFunction(v, 30)
+ "<br>" );
}
// Driver Code
let arr = [ 3, 2, 1 ];
let size = arr.length;
PrintMinimum(arr, size);
</script>
Выход:
 2