Найдите два целых числа таких, что в каждой заданной паре существует хотя бы одно

Опубликовано: 19 Сентября, 2022

Даны N пар целых чисел, каждое из которых находится в диапазоне от 1 до M , задача состоит в том, чтобы проверить, существуют ли два целых числа x и y , такие что хотя бы одно из целых чисел присутствует в каждой из пар.

Примеры:

Input: N = 7, M = 6, arr[] = {{5, 6}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}
Output: NO
Explanation: Can’t choose any x, or y because 
for each such pair you can find a given pair 
where both numbers are different from chosen integers.

Input: N = 5, M = 6, {{6, 4}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}
Output: YES
Explanation: Choose x = 5 and y = 3.
Because either x or y is present in all the pairs.

Подход 1: Проблема может быть решена на основе следующей идеи:

Consider the first pair of the array to be the desired pair (x, y). If there is a pair where none of the elements is present then one from that given pair must be the part of the desired pair.

So now there are total 4 elements which may form the desired pair. Check all possible combinations of pairs and find if any of them is the desired pair. 

Следуйте инструкциям, чтобы решить проблему:

  • Создайте 2 переменные (x1, y1), содержащие каждый из первых элементов массива.
  • Теперь перейдите от i = 0 к N-1 :
    • Проверьте, нет ли в паре ни одного из x1 или y1 .
    • Если приведенное выше условие верно, считайте элементы другой парой (x2, y2) .
  • Теперь проверьте все 6 возможных комбинаций x1, x2, y1 и y2.
    • Если одна из этих комбинаций существует в каждой заданной паре, то решение возможно.
    • В противном случае такой пары нет.

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

Временная сложность: O(N).
Вспомогательное пространство: O(1)

Подход 2: Идея этого подхода также аналогична упомянутой выше. Единственная разница в том, что:

In the previous case, we were using all the possible combinations. If observed carefully, we can conclude that there must be one value from the pair (x1, y1) and one value from (x2, y2) because if this is not done then one of the pairs will be neglected. 

So in this case we will be checking only for 4 possible pairs i.e., (x1, y2), (x1, x2), (y1, y2), and (x2, y1).

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  1. Рассмотрим первый элемент первой пары. Предположим, что (x1, y1) является парой, тогда рассмотрим x1 .
  2. Найдите пару, где x1 не существует.
  3. Рассмотрим эту пару как (x2, y2) и примем значение x2 :
    1. Проверьте все остальные пары, если (x1, x2) существует в каждой паре.
    2. Если выходит, выведите «Да», иначе повторите шаг 3 со значением y2.
  4. Если пара (x1, y2) выходит в каждой паре, выведите «Да», в противном случае повторите шаги с 1 по 3 со значением y1 .
  5. Если после описанной выше операции не осталось ни одной пары, то такая пара невозможна.

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

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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