Найдите такое число, чтобы максимум в массиве был минимально возможным после XOR
Опубликовано: 5 Января, 2022
Дан массив неотрицательных целых чисел. Выберите целое число P и выполните XOR P со всеми элементами массива. Задача состоит в том, чтобы выбрать P так, чтобы максимальное значение массива было минимально возможным после выполнения XOR всех элементов массива с P.
Примеры:
Input: arr = {3, 2, 1}
Output: 2
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