Посмотри на функцию count_pairs. Какая у неё сложность? Напиши более эффективный вариант.

Если функция count_pairs реализована классическим способом перебора всех пар элементов, то её временная сложность — O(n²), где n — количество элементов в списке. Это происходит потому, что для каждого элемента мы проходим по всем остальным, чтобы посчитать пары.

Более эффективный подход — использовать словарь (хэш-таблицу) для подсчёта количества элементов и затем вычислить количество пар по формуле для сочетаний из одинаковых элементов.

Пример оптимизированной функции на Python:

from collections import Counter

def count_pairs(arr):
    counts = Counter(arr)
    pairs = 0
    for count in counts.values():
        pairs += count * (count - 1) // 2  # число пар из count элементов
    return pairs

Сложность такого решения — O(n), так как мы один раз проходим по массиву для подсчёта и один раз по словарю для вычисления результата.