Подсчитайте способы выбрать триплеты пар так, чтобы первое или второе значения были различными.
Для заданного массива пар 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 — размер списка смежности.