---
# System prepended metadata

title: Find Max AND / XOR of a Pair in Array (2022.1.14)
tags: [CompetitiveProgramming, 競程筆記]

---

# Find Max AND / XOR of a Pair in Array (2022.1.14)
###### tags: `競程筆記` `CompetitiveProgramming`


## AND
### 想法
先分bit由大到小看，如果這個bit有兩個人以上，那就加到答案裡面。沒有這個bit的人就踢掉（以後不再看他）。
:::spoiler Code
```cpp=
int arr[100005], out[100005]; //出局
signed main(){
    int n;cin>>n;
    for (int i=1;i<=n;i++) cin>>arr[i];
    
    int ans = 0;
    for (int k=30;k>=0;k--){
        int cnt = 0;
        for (int i=1;i<=n;i++) if (!out[i]){
            if (arr[i] & (1<<k)) cnt++;
        }

        if (cnt>=2){
            ans += (1<<k);
            for (int i=1;i<=n;i++) if (!(arr[i] & (1<<k))) out[i] = true;
        }
    }
    cout<<ans<<endl;
}
```
:::

## XOR
喵了一眼網路上的做法，大多都是trie或神奇的超短東西
### 我的神奇做法
先舉例：1 4 5 6 12 13  輸出：13
首先一樣從大的bit開始看。根據xor的性質，要在答案中產生這個bit，需要有一個「有這個bit的數」和「沒這個bit的數」取xor。所以我們把數分成兩組。要記得先把重複的數字拿掉喔


| 8✓   | 8x     |
| ----- | ------- |
| 12 13 | 1 4 5 6 |

最佳答案一定是左邊某個數xor右邊某個數。


---

接著，我們看下一個bit。一樣再把左邊分成兩組，右邊分成兩組。


<table>
    <thead>
        <tr>
            <th colspan=2>8✓</th>
            <th colspan=2>8x</th> 
        </tr>
    </thead>
    <tbody>
        <tr>
            <th rowspan=1>4✓ (A組)</th>
            <th rowspan=1>4x (B組)</th>
            <th rowspan=1>4✓ (C組)</th>
            <th rowspan=1>4x (D組)</th>
        </tr>
        <tr>
        </tr>
        <tr>
            <td rowspan=1>12 13</td>
            <td rowspan=1> </td>
            <td rowspan=1>4 5 6</td>
            <td rowspan=1>1</td>
        </tr>
</table>

最佳答案(目前是8+4=12以上)一定是 「A配D」 或是 「B配C」兩者中較大的那個。所以我們就可以一直遞迴下去，找到最佳答案！以以上這個情形為例，答案一定是A和D，因為B和C其中一個為空。（成功剪枝）



---

<table>
    <thead>
        <tr>
            <th colspan=2>4✓</th>
            <th colspan=2>4x</th> 
        </tr>
    </thead>
    <tbody>
        <tr>
            <th rowspan=1>2✓ (A組)</th>
            <th rowspan=1>2x (B組)</th>
            <th rowspan=1>2✓ (C組)</th>
            <th rowspan=1>2x (D組)</th>
        </tr>
        <tr>
        </tr>
        <tr>
            <td rowspan=1> </td>
            <td rowspan=1>12 13</td>
            <td rowspan=1> </td>
            <td rowspan=1>1</td>
        </tr>
</table>

挖...「A和D」和「B和C」都湊不出來...怎麼辦？
用2這個bit沒辦法區分成兩組，我們只好捨棄這個bit了。但是下一個bit可能還有機會！把2的分組打回原形，再用1試試看！


---

<table>
    <thead>
        <tr>
            <th colspan=2>4✓</th>
            <th colspan=2>4x</th> 
        </tr>
    </thead>
    <tbody>
        <tr>
            <th rowspan=1>1✓ (A組)</th>
            <th rowspan=1>1x (B組)</th>
            <th rowspan=1>1✓ (C組)</th>
            <th rowspan=1>1x (D組)</th>
        </tr>
        <tr>
        </tr>
        <tr>
            <td rowspan=1>13</td>
            <td rowspan=1>12</td>
            <td rowspan=1>1 </td>
            <td rowspan=1> </td>
        </tr>
</table>

有了！這時候我們就能快樂的 return $~12 ~xor~ 1$ 了！


---

#### 一開始怎麼辦？

一開始我們還不知道最大的數是由哪個bit開始的...
<table>
    <thead>
        <tr>
            <th colspan=2>16✓</th>
            <th colspan=2>16x</th> 
        </tr>
    </thead>
    <tbody>
        <tr>
            <th rowspan=1>8✓ (A組)</th>
            <th rowspan=1>8x (B組)</th>
            <th rowspan=1>8✓ (C組)</th>
            <th rowspan=1>8x (D組)</th>
        </tr>
        <tr>
        </tr>
        <tr>
            <td rowspan=1> </td>
            <td rowspan=1> </td>
            <td rowspan=1>12 13 </td>
            <td rowspan=1>1 4 5 6 </td>
        </tr>
</table>

顯然醬就是捨棄A組和B組，用 C D 遞迴下去。
<table>
    <thead>
        <tr>
            <th colspan=2>16✓</th>
            <th colspan=2>16x</th> 
        </tr>
    </thead>
    <tbody>
        <tr>
            <th rowspan=1>8✓ (A組)</th>
            <th rowspan=1>8x (B組)</th>
            <th rowspan=1>8✓ (C組)</th>
            <th rowspan=1>8x (D組)</th>
        </tr>
        <tr>
        </tr>
        <tr>
            <td rowspan=1>24 25 26 </td>
            <td rowspan=1>16 18  </td>
            <td rowspan=1> </td>
            <td rowspan=1>  </td>
        </tr>
</table>

同理，如果只有A B兩組非空，就用 A B 遞迴下去。


---

#### 會不會看到1這個bit時，還有一組大小超過1？

不會，因為每一組都代表在那個bit有不一樣的0或1。如果有以上這個情況發生，那一定是數個相同的數字。


---

#### 這樣複雜度是多少？

我們的遞迴有 $log(a_i)$ 層，在每一層，每個數字都會被恰看過一次。所以時間和空間複雜度都是 $O(nlog(a_i))$。（只是這個實作方法常數有點大就是了）

![](https://i.imgur.com/pEfNBEn.png)



---

:::spoiler LeetCode AC
```cpp=
class Solution {
public:
    int arr[200005] ;
    int f(int k,vector<int> L,vector<int> R){

        if (L.empty() && R.empty()) return 0;
        if (L.size()==1 && R.size()==1) return L[0] ^ R[0];
        if (k<=0) return 0;

        vector<int> a,b,c,d;
        for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
        for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);

        if (a.empty() && b.empty()) return f(k-1,c,d);
        else if (c.empty() && d.empty()) return f(k-1,a,b);
        else if (a.size() && b.size() && c.size() && d.size()){
            return max(f(k-1,a,d),f(k-1,c,b));
        }else if (   (a.empty() || d.empty()) && (c.empty() || b.empty())  ){ 
            return f(k-1,L,R); // ?
        }else if ((a.empty() || d.empty())){
            return f(k-1,c,b);
        }else {
            return f(k-1,a,d);
        }

    }

    
    int findMaximumXOR(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        
        int maxn;
        int n = nums.size();
        for (int i=1;i<=n;i++) {
            arr[i] = nums[i-1];
            maxn = max(maxn,arr[i]);
        }
        vector<int> v,e;
        for (int i=1;i<=n;i++) v.push_back(arr[i]);


        int res = f(31,e,v);
        return res;
    }
};
```
:::

:::spoiler Full Code
```cpp=
// Cookie197 
// the people who invented competitive programmin must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
#define mod 998244353 
#define endl "\n"
#define inf 1e9
int arr[200005] ;
int f(int k,vector<int> L,vector<int> R){
    //cout<<"#"<<k<<"     "; 
    //for (int u:L) cout<<u<<" ";
    //cout<<"     ";
    //for (int u:R) cout<<u<<" ";
    //cout<<endl;


    if (L.empty() && R.empty()) return 0;
    if (L.size()==1 && R.size()==1) return L[0] ^ R[0];
    if (k<=0) return 0;

    vector<int> a,b,c,d;
    for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
    for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);
    
    if (a.empty() && b.empty()) return f(k-1,c,d);
    else if (c.empty() && d.empty()) return f(k-1,a,b);
    else if (a.size() && b.size() && c.size() && d.size()){
        return max(f(k-1,a,d),f(k-1,c,b));
    }else if (   (a.empty() || d.empty()) && (c.empty() || b.empty())   ){ 
        return f(k-1,L,R); 
    }else if ((a.empty() || d.empty())){
        return f(k-1,c,b);
    }else {
        return f(k-1,a,d);
    }
    
}

int maxn;
signed main(){
    int n;cin>>n;
    for (int i=1;i<=n;i++){
        cin>>arr[i]; maxn = max(maxn,arr[i]);
    }
    // you should remove dulplicates first

    vector<int> v,e;
    for (int i=1;i<=n;i++) v.push_back(arr[i]);
    int b = 0; while((1<<b)<=maxn) b++;
    
    
    int res = f(b,e,v);
    cout<<"ans=";
    cout<<res<<endl;
}
```
:::


## 延伸題 [CF 1625D Binary Spiders](https://codeforces.com/contest/1625/problem/D)

### 重要觀察
想要很多個數字的xor大於k，要先看「比k大的bit」
以k=5 (101) 為例，我們依照8以上的bit們的不同，來對陣列的數字進行分組。

:::spoiler Code
```cpp=
// Cookie197 
// the people who invented competitive programmin must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
#define mod 998244353 
#define endl "\n"
#define inf 1e9
int arr[300005] ;
vector<vector<int> > group;
map<int,int> pos;
pair<int,pii> z = mp(0,mp(0,0));
pair<int,pii> f(int k,vector<int> L,vector<int> R){

    if (L.empty() && R.empty()) return z;
    if (L.size()==1 && R.size()==1) return mp(L[0] ^ R[0],mp(pos[L[0]],pos[R[0]]));
    if (k<=0) return z;

    vector<int> a,b,c,d;
    for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
    for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);
    
    if (a.empty() && b.empty()) return f(k-1,c,d);
    else if (c.empty() && d.empty()) return f(k-1,a,b);
    else if (a.size() && b.size() && c.size() && d.size()){
        return max(f(k-1,a,d),f(k-1,c,b));
    }else if (   (a.empty() || d.empty()) && (c.empty() || b.empty())   ){ 
        return f(k-1,L,R); 
    }else if ((a.empty() || d.empty())){
        return f(k-1,c,b);
    }else {
        return f(k-1,a,d);
    }
}

pair<int,pii> max_xor(vector<int> v){
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    vector<int> e;
    return f(31,e,v);
}

int maxn;
vector<int> Ans;
map<int,int> m;
signed main(){
    Why_does_competitive_programming_even_exist;
    int n,k;cin>>n>>k;

    int tmp = k, lim = 0;
    while(tmp){
        tmp >>= 1;
        lim++;
    }

    int cnt = 0;
    for (int i=1;i<=n;i++){
        cin>>arr[i]; 
        pos[arr[i]] = i;
        if (m.count(arr[i]>>lim)){
            group[ m[(arr[i]>>lim)] ] .push_back(arr[i]);
        }
        else {
            vector<int> e;
            group.push_back(e);
            m[(arr[i]>>lim)] = cnt;
            group[cnt].push_back(arr[i]);
            cnt++;
        }
    }

    if (k==0){
        cout<<n<<endl;
        for (int i=1;i<=n;i++) cout<<i<<" ";
        cout<<endl; return 0;
    }
    
    int ans = 0;
    for (int u=0;u<group.size();u++){
        if (group[u].size()==1) {
            ans++;
            Ans.push_back(pos[group[u][0]]);
        }
        else {
            pair<int,pii> p = max_xor(group[u]);
            if (p.first >= k) {
                ans+=2;
                Ans.push_back(p.second.first);
                Ans.push_back(p.second.second);
            }else{
                ans++; Ans.push_back(pos[group[u][0]]);
            }
        }
    }

    if (ans<2) {
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
    for (int u:Ans) cout<<u<<" ";
    cout<<endl;
    
}
```
:::