Find pair whose bitwise OR and bitwise AND follows the given condition

By Ann Roberts On Nov 24, 2022

Given 2 arrays arr1[] and arr2[], of size N and M respectively, the task is to find a pair of value (say a and b) such that the following conditions are satisfied:

(a | b) ≤ arr1[i]for all values of i in the range [0, N-1].
(a & b) ≥ arr2[j] for all values of j in the range [0, M-1].

Examples:

Input: arr1[] = { 6, 9, 7, 8}, arr2[] = {2, 1, 3, 4}
Output: 4 5
Explanation: 4 | 5= 5 and 4 & 5 = 4
Since values of their bitwise OR <= is less than arr1[] elements and also value of their bitwise AND ≥ less than arr2[] elements.Hence it forms a valid pair. other possible output may be :
4 | 6 = 6 and 4 & 6 =4 Again since 6 is less than arr1[] elements and 4 >= all other arr2[] elements. Hence it also forms a valid pair.

Input: arr1[] = {1, 9, 7}, arr2[] = {2, 4, 3}
Output: -1
Explanation: No such pair exists.

Approach: To solve the problem follow the below idea:

Since we know that: (a | b) ≥ max(a, b) (a & b) ≤ min(a, b). If we can prove that there exists a pair {a, b} (assuming b > a)such that b ≤ minimum of all other array OR elements and a ≥ maximum of all array AND elements then it would also satisfy all other elements

Follow the below steps to solve the problem:

Find the minimum element of the first array and the maximum element of the second array.
Then check the condition, if b ≥ a then print b and a.
Otherwise, print “-1”.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void findPair(int arr1[], int arr2[], int n, int m)

{

int minimum_or_element = INT_MAX;

int maximum_and_element = INT_MIN;

for (int i = 0; i < n; i++) {

if (arr1[i] < minimum_or_element) {

minimum_or_element = arr1[i];

}

for (int i = 0; i < m; i++) {

if (arr2[i] > maximum_and_element) {

maximum_and_element = arr2[i];

}

if (minimum_or_element >= maximum_and_element) {

cout << maximum_and_element << " "

<< minimum_or_element << endl;

}

else {

cout << -1 << endl;

}

int main()

{

int arr1[] = { 1, 9, 7 };

int arr2[] = { 2, 4, 3 };

int n = sizeof(arr1) / sizeof(int);

int m = sizeof(arr2) / sizeof(int);

findPair(arr1, arr2, n, m);

return 0;

}

Time Complexity: O(N + M) to traverse both arrays and find the minimum and maximum values respectively.
Auxiliary Space: O(N + M) storing both array elements.

Related Articles: