Найдите пару, в которой побитовое ИЛИ и побитовое И следуют заданному условию

Опубликовано: 25 Февраля, 2023

Учитывая 2 массива arr1[] и arr2[] размера N и M соответственно, задача состоит в том, чтобы найти пару значений (скажем , a и b ), такую, что выполняются следующие условия:

(а | б) ≤ arr1[i]для всех значений i в диапазоне [0, N-1].
(а и б) ≥ обр2[j] для всех значений j в диапазоне [0, M-1].

Примеры:

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.

Подход: Чтобы решить проблему, следуйте следующей идее:

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

Выполните следующие шаги, чтобы решить проблему:

Найдите минимальный элемент первого массива и максимальный элемент второго массива.
Затем проверьте условие, если b ≥ a , то выведите b и a .
В противном случае выведите «-1».

Ниже приведена реализация описанного выше подхода.

C++

// C++ to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find pair
// Satisfying the condition
 
void 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 code
int 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 approach
import 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 condition
def 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 elements
arr1 = [1, 9, 7]
# Denoting bitwise AND elements
arr2 = [2, 4, 3]
n = len(arr1)
m = len(arr2)
# Function call
findPair(arr1, arr2, n, m)
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# implementation
using 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 approach
const INT_MAX = 2147483647;
const INT_MIN = -2147483647 - 1;
 
// Function to find pair
// Satisfying the condition
 
const 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 elements
let arr1 = [1, 9, 7];
// Denoting bitwise AND elements
let arr2 = [2, 4, 3];
let n = arr1.length;
let m = arr2.length;
// Function call
findPair(arr1, arr2, n, m);
 
// This code is contributed by rakeshsahni

Сложность времени : O(N + M) для обхода обоих массивов и поиска минимального и максимального значений соответственно.
Вспомогательное пространство : O (N + M), хранящее оба элемента массива.

Статьи по Теме:

Введение в массивы - учебные пособия по структурам данных и алгоритмам
Введение в побитовые алгоритмы - учебные пособия по структурам данных и алгоритмам

Technical Scripter

Найдите пару, в которой побитовое ИЛИ и побитовое И следуют заданному условию

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ