## Intuition The problem requires us to determine if we can make at least two elements in the array equal by performing a bitwise AND operation with a given number `x`. The key insight is to explore the effects of the AND operation and check for potential duplicates after applying this operation. ## Approach 1. **Initial Check for Duplicates**: - First, check if there are already any duplicates in the array. If there are, the answer is `0` because no operations are needed. 2. **Effect of AND Operation**: - For each element `a[i]`, compute `a[i] & x`. This operation might create duplicates with other elements in the array or with other `a[j] & x`. 3. **Check for Duplicates After AND**: - Use a hash map to track the original elements and their AND results. - If `a[i] & x` matches any other `a[j]` or `a[j] & x`, then we can achieve duplicates with `1` operation. 4. **Determine the Minimum Operations**: - If any `a[i] & x` equals another element `a[j]`, then we can achieve duplicates with `1` operation. - If no such pair exists, return `-1` as it is impossible to create duplicates. ## Complexity - **Time Complexity**: O(n), where `n` is the number of elements in the array. We perform constant time operations for each element. - **Space Complexity**: O(n), due to the use of hash maps to track elements and their AND results. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; vector a(n); unordered_map original_count, and_count; for (int i = 0; i < n; ++i) { cin >> a[i]; original_count[a[i]]++; } // Check if there are any duplicates initially for (const auto& [key, value] : original_count) { if (value > 1) { cout << 0 << '\n'; return 0; } } // Check for duplicates after AND operation for (int i = 0; i < n; ++i) { int and_result = a[i] & x; if (and_result != a[i]) { if (original_count[and_result] > 0) { cout << 1 << '\n'; return 0; } and_count[and_result]++; } } // Check if any AND results themselves have duplicates for (const auto& [key, value] : and_count) { if (value > 1) { cout << 1 << '\n'; return 0; } } // If no duplicates can be formed cout << -1 << '\n'; return 0; } ``` This solution efficiently checks for duplicates both in the original array and after applying the AND operation, ensuring the minimal number of operations is determined.

And

Problem Details