Дана последовательность из N чисел. Посчитайте, сколько в ней пар элементов, равных друг другу

def countpairs(a):
    '''
    Наивный алгоритм полного перебора
    Сложность O(N^2)
    
    In [1]: import random
    
    In [2]: arr = [random.randint(1,10000) for _ in range(10000)]
    
    In [3]: %timeit -n 10 -r 1 countpairs(arr)
    7.86 s ± 0 ns per loop (mean ± std. dev. of 1 run, 10 loops each)
    '''
    
    counter = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                counter += 1
    return counter
 
 
def countpairs2(a):
    '''
    Сложность O(N^2)
    Работает чуть быстрее чем перебор в два цикла за счет использования count в
    качестве второго цикла.
    
    In [1]: import random
    
    In [2]: arr = [random.randint(1,10000) for _ in range(10000)]
    
    In [3]: %timeit -n 10 -r 1 countpairs2(arr)
    3.79 s ± 0 ns per loop (mean ± std. dev. of 1 run, 10 loops each)
    '''
    
    return sum(a.count(x) - 1 for x in a) // 2
 
 
def countpairs3(a):
    '''
    Сложность O(N) на создание словаря счетчика + O(N) на подсчет пар
    Сложность по памяти O(N)
    
    In [1]: import random
    
    In [2]: arr = [random.randint(1,10000) for _ in range(10000)]
    
    In [3]: %timeit -n 10 -r 10 countpairs3(arr)
    7.1 ms ± 293 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
    '''
    
    cnt = {}
    for num in a:
        cnt.setdefault(num,0)
        cnt[num] += 1
    
    return sum(cnt[num] * (cnt[num] - 1)//2  for num in cnt)
 
 
from collections import Counter
 
def countpairs4(a):
    '''
    Сложность O(N) на создание словаря счетчика + O(N) на подсчет пар
    Сложность по памяти O(N)
    
    In [1]: import random
    
    In [2]: arr = [random.randint(1,10000) for _ in range(10000)]
    
    In [3]: %timeit -n 10 -r 10 countpairs4(arr)
    5.59 ms ± 369 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
    '''
    
    
    cnt = Counter(a)
    return sum(
            cnt[num] * (cnt[num] - 1)//2  for num in cnt
    )
 
 
 
def countpairs5(arr):
    '''
    Сложность O(N log N) на сортировку + O(N) на подсчет пар
    
    In [1]: import random
    
    In [2]: arr = [random.randint(1,10000) for _ in range(10000)]
    
    In [3]: %timeit -n 10 -r 10 countpairs5(arr)
    9.21 ms ± 351 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
    '''
    
    arr = sorted(arr)
    len_a = len(arr)
    pairs, curr = 0, 0
    cnt = 0
    
    while curr < len_a - 1:
        cnt = 1
        next_ = curr + 1
        # сравниваем последующие числа с текущим
        while next_ < len(arr):
            # пока числа равны - ведем подсчет
            if arr[next_] == arr[curr]:
                cnt += 1
                next_ +=1
            # иначе - другое число - прерываемся
            else:
                break
        
        #  инкрементируем общий счетчик пар
        # по формуле возможных пар для этого числа
        pairs += cnt * (cnt - 1)//2 
        # начинаем с первого a[next_] неравного текущему a[curr]
        curr = next_
    return pairs