对于给定数组的任何排列，最大化第一个元素的按位与，并保留其余元素 _按位与

本文概述

C ++
Java
Python3
C#

给定一个由N个整数组成的数组arr[]，其任务是找到第一个元素的位与的最大值，其余元素的补全对这个数组的任何排列，即。

A1 &(~A2) & (~A3) & ……& (~An)

例子：

【对于给定数组的任何排列，最大化第一个元素的按位与，并保留其余元素】输入：arr [] = {1, 2, 4, 8, 16}
输出：16
说明：
对于排列{16, 1, 2, 4, 8}, 可以获得表达式的最大值。
输入：arr [] = {0, 2, 3, 4, 9, 8}
输出：4
说明：
对于排列{4, 8, 9, 3, 2, 0}, 可以获得表达式的最大值

简单的方法:解决这个问题的最简单的方法是生成给定数组的所有可能的排列，并找到每个排列所需的值，并打印其中的最大值。
并找到每个排列所需的值, 并在其中列出最大值。
时间复杂度：O(N * N!)
辅助空间：O(N)
高效方法：可以通过以下观察来优化上述方法：

表达方式一种1＆(?A2)＆(?A3)＆……＆(?A?)完全取决于A的值1.
因此, 要从表达式中获得最大值, 请选择A1这样它有设置位具有尽可能高的重要性, 而在所有其他数组元素中未设置。
由于剩余数组元素的顺序无关紧要, 请打印具有获得的A的任何排列1作为第一个元素。

解析：对于arr [] = {1, 2, 4, 8, 16}
数组元素的二进制表示：
(16)10 =(10000)2
(8)10 =(01000)2
(4)10 =(00100) )2
(2)10 =(00010)2
(1)10 =(00001)2
可以看出, 16具有最高有效置位位, 而在所有其他数组元素中未置位。因此, 给定置换的所需置换将包含16作为第一个元素。因此, 对于以16作为第一个元素的置换, 所需的按位与最大, 在这种情况下等于16。

下面是上述方法的实现：
C ++

//C++ Program to implement //the above approach #include < bits/stdc++.h> using namespace std; #define size_int 32 //Function to maximize the value for //the given function and the array elements int functionMax( int arr[], int n) { //Vector array to maintain which bit is set //for which integer in the given array by //saving index of that integer vector< int> setBit[32]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < size_int; j++) { //Check if j-th bit is set for //i-th integer if (arr[i] & (1 < < j)) //Push the index of that //integer in setBit[j] setBit[j].push_back(i); } } //Find the element having //highest significant set bit //unset in other elements for ( int i = size_int; i> = 0; i--) { if (setBit[i].size() == 1) { //Place that integer at 0-th index swap(arr[0], arr[setBit[i][0]]); break ; } } //Store the maximum AND value int maxAnd = arr[0]; for ( int i = 1; i < n; i++) { maxAnd = maxAnd & (~arr[i]); } //Return the answer return maxAnd; } //Driver Code int main() { int arr[] = { 1, 2, 4, 8, 16 }; int n = sizeof arr /sizeof arr[0]; //Function call cout < < functionMax(arr, n); return 0; }

Java

//Java Program to implement //the above approach import java.util.*; class GFG{ static final int size_int = 32 ; //Function to maximize the value for //the given function and the array elements static int functionMax( int arr[], int n) { //Vector array to maintain which bit is set //for which integer in the given array by //saving index of that integer Vector< Integer> []setBit = new Vector[ 32 + 1 ]; for ( int i = 0 ; i < setBit.length; i++) setBit[i] = new Vector< Integer> (); for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < size_int; j++) { //Check if j-th bit is set for //i-th integer if ((arr[i] & ( 1 < < j))> 0 ) //Push the index of that //integer in setBit[j] setBit[j].add(i); } } //Find the element having //highest significant set bit //unset in other elements for ( int i = size_int; i> = 0 ; i--) { if (setBit[i].size() == 1 ) { //Place that integer at 0-th index swap(arr, 0 , setBit[i].get( 0 )); break ; } } //Store the maximum AND value int maxAnd = arr[ 0 ]; for ( int i = 1 ; i < n; i++) { maxAnd = maxAnd & (~arr[i]); } //Return the answer return maxAnd; }static int [] swap( int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; }//Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 4 , 8 , 16 }; int n = arr.length; //Function call System.out.print(functionMax(arr, n)); } } //This code is contributed by PrinciRaj1992

Python3

# Python 3 Program to # implement the above approach # Function to maximize the # value for the given function # and the array elements def functionMax(arr, n):# Vector array to maintain # which bit is set for which # integer in the given array by # saving index of that integer setBit = [[] for i in range ( 32 )] for i in range (n): for j in range ( 32 ):# Check if j-th bit is # set for i-th integer if (arr[i] & ( 1 < < j)):# Push the index of that # integer in setBit[j] setBit[j].append(i) # Find the element having # highest significant set bit # unset in other elements i = 31while (i> = 0 ): if ( len (setBit[i]) = = 1 ):# Place that integer # at 0-th index temp = arr[ 0 ] arr[ 0 ] = arr[setBit[i][ 0 ]] arr[setBit[i][ 0 ]] = temp break i - = 1 # Store the maximum # AND value maxAnd = arr[ 0 ] for i in range ( 1 , n, 1 ): maxAnd = (maxAnd & (~arr[i])) # Return the answer return maxAnd # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 4 , 8 , 16 ] n = len (arr) # Function call print (functionMax(arr, n)) # This code is contributed by bgangwar59

//C# Program to implement //the above approach using System; using System.Collections.Generic; class GFG{ static readonly int size_int = 32; //Function to maximize the value for //the given function and the array elements static int functionMax( int []arr, int n) { //List array to maintain which bit is set //for which integer in the given array by //saving index of that integer List< int> []setBit = new List< int> [32 + 1]; for ( int i = 0; i < setBit.Length; i++) setBit[i] = new List< int> (); for ( int i = 0; i < n; i++) { for ( int j = 0; j < size_int; j++) { //Check if j-th bit is set for //i-th integer if ((arr[i] & (1 < < j))> 0) //Push the index of that //integer in setBit[j] setBit[j].Add(i); } } //Find the element having //highest significant set bit //unset in other elements for ( int i = size_int; i> = 0; i--) { if (setBit[i].Count == 1) { //Place that integer at 0-th index swap(arr, 0, setBit[i][0]); break ; } } //Store the maximum AND value int maxAnd = arr[0]; for ( int i = 1; i < n; i++) { maxAnd = maxAnd & (~arr[i]); } //Return the answer return maxAnd; }static int [] swap( int []arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; }//Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 4, 8, 16 }; int n = arr.Length; //Function call Console.Write(functionMax(arr, n)); } } //This code is contributed by Rajput-Ji

输出如下：