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

2021年4月29日18:05:34 发表评论 864 次浏览

本文概述

给定一个由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 = 31
     
     while (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#

//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

输出如下：

16

时间复杂度：

O(N * sizeof(int)), 其中sizeof(int)为32

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: