Подсчитайте способы выбрать триплеты пар так, чтобы первое или второе значения были различными.

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

Для заданного массива пар arr[] размера N (N ≥ 3), где каждый элемент пары не превосходит N и каждая пара уникальна, задача состоит в том, чтобы определить количество способов выбрать триплеты из заданных N пар, которые удовлетворяют хотя бы одно из следующих условий:

  • Первое значение ( a ) каждой пары должно быть различным.
  • Второе значение ( b ) каждой пары должно быть различным.

Примеры:

Input: N = 4, arr[] = {{2, 4}, {3, 4}, {2, 1}, {1, 4}} 
Output: 2
Explanation: The valid triplets are {{2, 4}. {3, 4}, {1, 4}} 
and {{3, 4}, {2, 1}, {1, 4}}

Input: N = 5, arr[] = {{1, 4}, {2, 4}, {3, 3}, {4, 2}, {1, 2}}
Output: 8

Подход: используйте приведенную ниже идею для решения проблемы.

The total number of triplets possible is n*(n – 1)*(n – 2)/6. So we can count the number of invalid pairs for the triplets and subtract that count from the total triplets possible

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

  • Создайте два 2D-вектора, чтобы вести учет пар в данном массиве.
  • Сохраните пары с одинаковым первым значением в первом 2D-векторе и пары с одинаковым вторым значением во втором 2D-векторе.
  • Инициализируйте ans = N*(N – 1)*(N – 2)/6 , возможное количество пар.
  • Пройдитесь по первому двумерному вектору и вычислите количество троек, которые невозможны для каждого значения в данном массиве.
  • Вычтите количество недопустимых пар из ответа .
  • Вернуть ответ как окончательный ответ.

Ниже приведена реализация ab

подход:

Временная сложность: O(N), цикл выполняется один раз для каждого первого значения.
Вспомогательное пространство: O(N), где N — размер списка смежности.

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