Блог пользователя _humblefool_

Автор _humblefool_, история, 3 года назад, По-английски

Given an array A of N elements, you can pick at most one element of the array and increment or decrement it by any value. The task is to maximize the AND of the resulting array.

Note: AND of the array is defined as the bitwise AND(&) of all the array elements.

Constraints: 2 ≤ N ≤ 2 * 10^5 0 ≤ A[i] ≤ 2 * 10^9

  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

No problem link, no help.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

To anyone who is interested in seeing the problem : Problem Link

Approach:

Think about binary representation of numbers, here point to note is the bit positions such that all the numbers have 1 at that position except 1 number that has a 0.Such bit positions can be changed to have all 1 by adding pow(2,i) (where i is the bit position) to that number which currently has a 0 at that location , this will increase the overall AND.

For each number maintain a set that tells you at these bits position the above property is satisfied for the number and then try to find the one that will help in setting the AND to the maximum value as we can modify only one number.

Code :

  class Solution{
      public:
      int maxAnd(int N, vector<int> A){
         int vl=0;
         vector<vector<int>>tmp(N);
         for(int i=0;i<31;i++){
            int cnt = 0,in;
            for(int j=0;j<A.size();j++){
                if(((A[j]>>i)&1LL) == 0){
                    cnt++;
                    in = j;
                }
            }
            
            if(cnt == 1){
                tmp[in].push_back(i);
            }
            
            if(cnt == 0){
                vl += pow(2,i);
            }
        }
        
        int mx = 0;
        for(int i=0;i<N;i++){
            int tmpvl = 0;
            for(auto j:tmp[i]){
                tmpvl += pow(2,j);
            }
            mx = max(mx,tmpvl);
        }
        
        vl += mx;
        
        return vl;
    }
    
  };
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'll use $$$\land$$$ instead of & for notational convenience.

Let $$$P_i = A_1 \land \ldots \land A_{i - 1}$$$ and $$$S_i = A_{i + 1} \land \ldots \land A_n$$$, where the bitwise and of the empty array is $$$2^{31} - 1$$$.

If you don't change any element, the answer is the bitwise and of everything in the array.

Otherwise, if you change $$$A_i$$$ to $$$A_i'$$$, then the new answer becomes $$$P_i \land A_i' \land S_i$$$, and this is maximized if $$$A_i' = P_i \land S_i$$$, for example. So the answer becomes $$$\max(S_0, P_1 \land S_1, P_2 \land S_2, \ldots, P_n \land S_n)$$$, and this can be computed in $$$O(n)$$$ time.