Блог

Задано N целых чисел. Триплет чисел — это набор из трех чисел, сумма которых делится на константу M. Выясните, у скольких различных триплетов чисел из заданных N целых чисел их сумма делится на M. Какой был бы оптимальный алгоритм для нахождения ответа на эту проблему?

Пожалуйста, обратите внимание: каждый элемент рассматривается как различный, независимо от их фактического значения.

Это ссылка на актуальную проблему

Существует O (N M ^ 2) решение.

Сначала создайте массив C [M], где C [i] содержит количество входных чисел, которые равны i mod M. Это занимает O (N) времени.

Затем для каждого i <= j <= k с i j k = 0 mod M, посчитайте тройки (a, b, c) с a = i (mod M), b = j (mod M), c = k (mod M).

Мы можем сделать это эффективно, перебрав i и j и найдя уникальное k, которое приводит к тому, что сумма равна 0 (mod M), игнорируя комбинацию, если k<j. Мы должны быть осторожны при подсчете, чтобы убедиться, что мы считаем уникальные тройки; если i, j, k различны, количество троек равно просто C [i] * C [j] * C [k], но если два или более индексов одинаковы, мы должны быть осторожны, чтобы не допустить повторного использования одного и того же числа. Например, если i = j!=k, то есть choose(C[i], 2) * C [k] троек.

Вот полный код, который выдает правильный ответ 26 для данного тестового примера:

 def choose2(n):
    return n * (n-1) // 2

def choose3(n):
    return n * (n-1) * (n-2) // 6

def triples(A, M):
    C = [0] * M
    for a in A:
        C[a % M]  = 1
    T = 0
    for i in range(M):
        for j in range(i, M):
            k = (-i - j) % M
            if k < j:
                continue
            if i == j == k:
                T  = choose3(C[i])
            elif i == j:
                T  = choose2(C[i]) * C[k]
            elif j == k:
                T  = C[i] * choose2(C[j])
            else:
                T  = C[i] * C[j] * C[k]
    return T

print(triples([1, 10, 4, 3, 2, 5, 0, 1, 9, 5], 5))
  

Сначала я бы вычислил остаток для каждого числа после деления его на M. Затем я бы отсортировал все N чисел по их остаткам.

Это N * логарифмическая (N) стоимость.

Затем для каждой пары чисел я бы искал, есть ли соответствующий остаток среди всех чисел, который даст мне сумму, кратную M.

Существует N ^ 2 пары, и каждый поиск представляет собой двоичный журнал поиска (N).

Итак, я вижу решение стоимостью N ^ 2 * log (N), но, возможно, есть что-то более сложное и дешевое.