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++
// C++ to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find pair// Satisfying the conditionvoid findPair(int arr1[], int arr2[], int n, int m){ // Initializing to maximum value int minimum_or_element = INT_MAX; // Initializing to minimum value int maximum_and_element = INT_MIN; // Finding the minimum element in arr1 for (int i = 0; i < n; i++) { if (arr1[i] < minimum_or_element) { minimum_or_element = arr1[i]; } } // Finding the maximum element in arr2 for (int i = 0; i < m; i++) { if (arr2[i] > maximum_and_element) { maximum_and_element = arr2[i]; } } // Checking the condition that b>=a if (minimum_or_element >= maximum_and_element) { cout << maximum_and_element << " " << minimum_or_element << endl; } else { // If a>b print -1 cout << -1 << endl; }}// Driver codeint main(){ // Denoting bitwise OR elements int arr1[] = { 1, 9, 7 }; // Denoting bitwise AND elements int arr2[] = { 2, 4, 3 }; int n = sizeof(arr1) / sizeof(int); int m = sizeof(arr2) / sizeof(int); // Function call findPair(arr1, arr2, n, m); return 0;} |
Java
// Java Code for the above approachimport java.io.*;class GFG { // Function to find pair // Satisfying the condition public static void findPair(int[] arr1, int[] arr2, int n, int m) { // Initializing to maximum value int minimum_or_element = Integer.MAX_VALUE; // Initializing to minimum value int maximum_and_element = Integer.MIN_VALUE; // Finding the minimum element in arr1 for (int i = 0; i < n; i++) { if (arr1[i] < minimum_or_element) { minimum_or_element = arr1[i]; } } // Finding the maximum element in arr2 for (int i = 0; i < m; i++) { if (arr2[i] > maximum_and_element) { maximum_and_element = arr2[i]; } } // Checking the condition that b>=a if (minimum_or_element >= maximum_and_element) { System.out.println(maximum_and_element + " " + minimum_or_element); } else { // If a>b print -1 System.out.println(-1); } } public static void main (String[] args) { // Denoting bitwise OR elements int[] arr1 = { 1, 9, 7 }; // Denoting bitwise AND elements int[] arr2 = { 2, 4, 3 }; int n = arr1.length; int m = arr2.length; // Function call findPair(arr1, arr2, n, m); }}// This code is contributed by lokeshmvs21. |
Python3
# Python to implement the approach# Function to find pair# Satisfying the conditiondef findPair(arr1, arr2, n, m): # Initializing to maximum value minimum_or_element = 1e9 + 7 # Initializing to minimum value maximum_and_element = -(1e9 + 7) # Finding the minimum element in arr1 for i in range(0, n): if (arr1[i] < minimum_or_element): minimum_or_element = arr1[i] # Finding the maximum element in arr2 for i in range(0, m): if (arr2[i] > maximum_and_element): maximum_and_element = arr2[i] # Checking the condition that b>=a if (minimum_or_element >= maximum_and_element): print(maximum_and_element, end=" ") print(minimum_or_element) else: # If a>b print -1 print(-1)# Driver code# Denoting bitwise OR elementsarr1 = [1, 9, 7]# Denoting bitwise AND elementsarr2 = [2, 4, 3]n = len(arr1)m = len(arr2)# Function callfindPair(arr1, arr2, n, m)# This code is contributed by Samim Hossain Mondal. |
C#
// C# implementationusing System;public class GFG { // Function to find pair // Satisfying the condition public static void findPair(int[] arr1, int[] arr2, int n, int m) { // Initializing to maximum value int minimum_or_element = Int32.MaxValue; // Initializing to minimum value int maximum_and_element = Int32.MinValue; // Finding the minimum element in arr1 for (int i = 0; i < n; i++) { if (arr1[i] < minimum_or_element) { minimum_or_element = arr1[i]; } } // Finding the maximum element in arr2 for (int i = 0; i < m; i++) { if (arr2[i] > maximum_and_element) { maximum_and_element = arr2[i]; } } // Checking the condition that b>=a if (minimum_or_element >= maximum_and_element) { Console.WriteLine(maximum_and_element + " " + minimum_or_element); } else { // If a>b print -1 Console.WriteLine(-1); } } static public void Main() { // Denoting bitwise OR elements int[] arr1 = { 1, 9, 7 }; // Denoting bitwise AND elements int[] arr2 = { 2, 4, 3 }; int n = arr1.Length; int m = arr2.Length; // Function call findPair(arr1, arr2, n, m); }}// This code is contributed by ksam24000 |
Javascript
// JavaScript to implement the approachconst INT_MAX = 2147483647;const INT_MIN = -2147483647 - 1;// Function to find pair// Satisfying the conditionconst findPair = (arr1, arr2, n, m) => { // Initializing to maximum value let minimum_or_element = INT_MAX; // Initializing to minimum value let maximum_and_element = INT_MIN; // Finding the minimum element in arr1 for (let i = 0; i < n; i++) { if (arr1[i] < minimum_or_element) { minimum_or_element = arr1[i]; } } // Finding the maximum element in arr2 for (let i = 0; i < m; i++) { if (arr2[i] > maximum_and_element) { maximum_and_element = arr2[i]; } } // Checking the condition that b>=a if (minimum_or_element >= maximum_and_element) { console.log(`${maximum_and_element} ${minimum_or_element}<br/>`); } else { // If a>b print -1 console.log("-1<br/>"); }}// Driver code// Denoting bitwise OR elementslet arr1 = [1, 9, 7];// Denoting bitwise AND elementslet arr2 = [2, 4, 3];let n = arr1.length;let m = arr2.length;// Function callfindPair(arr1, arr2, n, m);// This code is contributed by rakeshsahni |
-1
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:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Introduction to Bitwise Algorithms – Data Structures and Algorithms Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
