AND Pairs
Time limit: 1 s.
Memory limit: 256 MB
You are given \(n\) integers \(a_1, a_2, \dots, a_n\).
Find the maximum value of \(a_i ~\&~ a_j\) over all pairs of distinct indices \(i \ne j\).
Here \(\&\) denotes the bitwise AND operation.
The bitwise AND operation compares two integers bit by bit. For each bit position:
- if both bits are \(1\), the resulting bit is \(1\);
- otherwise, the resulting bit is \(0\).
For example, \(10 = (1010)_2\) and \(15 = (1111)_2\), so \(10 ~\&~ 15 = (1010)_2 = 10\).
Input
The first line contains one integer \(n\) (\(2 \le n \le 10^5\)).
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \lt 2^{30}\)).
Output
Print one integer: the maximum possible value of \(a_i ~\&~ a_j\) over all pairs of distinct indices.
Scoring
| Group | Add. constraints | Points |
|---|---|---|
| \(1\) | All numbers are equal | \(4\) |
| \(2\) | \(n \le 1000\) | \(7\) |
| \(3\) | \(n \le 7000\) | \(10\) |
| \(4\) | \(a_i \le 1023\) | \(12\) |
| \(5\) | All numbers are of the form \(2^k - 1\), where \(k\) may differ between numbers | \(14\) |
| \(6\) | Exactly two numbers have bit \(29\) (the largest possible bit) equal to \(1\) | \(15\) |
| \(7\) | There are at most \(1000\) distinct values | \(17\) |
| \(8\) | — | \(21\) |
Example
Input
5
10 6 15 3 8
Output
10
Note
The bitwise AND of two numbers keeps only the bits that are equal to \(1\) in both numbers.
For the sample, the numbers in binary are: \(10 = (1010)_2\), \(6 = (0110)_2\), \(15 = (1111)_2\), \(3 = (0011)_2\), and \(8 = (1000)_2\).
Now check all pairs:
- \(10 ~\&~ 6 = 2\), because \((1010)_2 ~\&~ (0110)_2 = (0010)_2\).
- \(10 ~\&~ 15 = 10\), because \((1010)_2 ~\&~ (1111)_2 = (1010)_2\).
- \(10 ~\&~ 3 = 2\), because \((1010)_2 ~\&~ (0011)_2 = (0010)_2\).
- \(10 ~\&~ 8 = 8\), because \((1010)_2 ~\&~ (1000)_2 = (1000)_2\).
- \(6 ~\&~ 15 = 6\), because \((0110)_2 ~\&~ (1111)_2 = (0110)_2\).
- \(6 ~\&~ 3 = 2\), because \((0110)_2 ~\&~ (0011)_2 = (0010)_2\).
- \(6 ~\&~ 8 = 0\), because \((0110)_2 ~\&~ (1000)_2 = (0000)_2\).
- \(15 ~\&~ 3 = 3\), because \((1111)_2 ~\&~ (0011)_2 = (0011)_2\).
- \(15 ~\&~ 8 = 8\), because \((1111)_2 ~\&~ (1000)_2 = (1000)_2\).
- \(3 ~\&~ 8 = 0\), because \((0011)_2 ~\&~ (1000)_2 = (0000)_2\).
The maximum among these values is \(10\), achieved by the pair \((10, 15)\).
Solution
Build the answer from the highest bit to the lowest. Temporarily add the current bit to the answer mask and count how many input values contain all bits of that mask.
If at least two values contain them, those two values have an AND that contains the whole mask, so the bit can remain. Otherwise, remove it.
The complexity is \(O(30N)\) time and \(O(N)\) memory.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int& value : a) {
cin >> value;
}
int answer = 0;
for (int bit = 29; bit >= 0; bit--) {
int candidate = answer | (1 << bit);
int count = 0;
for (int value : a) {
if ((value & candidate) == candidate) {
count++;
}
}
if (count >= 2) {
answer = candidate;
}
}
cout << answer << '\n';
}