Найти делимые суммы пар в массиве в O (n) времени

Question

Вам задан массив из n целых чисел a0, a1, .. an и положительное целое число k. Найдите и распечатайте количество пар (i,j) где и i+j равномерно делится на k (что составляет i+j % k == 0). Эта проблема взята из here.

Нам нужно решение в O(n) времени.

Объяснение состоит в том, что мы можем сделать это, разделив элементы на ведра в зависимости от их mod k. Например, у вас есть элементы: 1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9 
mod 3 == 1 : 1 4 
mod 3 == 2 : 2 5 

Затем он сказал:

Теперь вы можете сделать пар, как так: Элементы с модник 3 == 0 будет соответствовать с элементами с (3 - 0) мод к = 0, так что другие элементы в списке мод 3 == 0, так как: (3, 6) (3, 9) (6, 9)

Далее:

Там будут n * (n - 1)/2 такие пары, где n - длина списка , потому что список тот же, и i! = J. Элементы с mod 3 == 1 будут совпадать с элементами с (3 - 1) mod k = 2, поэтому элементы в списке mod 3 == 2, например: (1, 2) (1, 5) (4 , 2) (4, 5)

Это имеет смысл, что (3, 6) (3, 9) (6, 9) (all items in the 0th bucket be paired) поскольку (a + b)% k = 0 = a % k + b % k.

Не ясно, как другие пары были сгенерированы комбинацией элементов в 1-м (mod 3 == 1) и 2-м (mod 3 == 2) ведро и почему было бы n * (n - 1)/2 пары. Есть ли другой (лучший) метод?

Этот вопрос подходит для Math Stackexchange, о существовании которого я не знал, прежде чем размещать вопрос.

Answer 1

У вас есть n * (n - 1)/2 пар, потому что все (n) могут быть соединены со всеми остальными (n-1); но поскольку порядок не имеет значения, мы не будем считать зеркальные пары делением на два.

Также остатки по одному и тому же коэффициенту суммируются при суммировании числителей, но напоминание не может быть больше, чем частное. Напоминание 3 в делении на 3 на самом деле является напоминанием о 0.

Ответ очень умный, вы, вероятно, можете сделать его на несколько процентов быстрее при оптимизации на низком уровне; например, реализовать выделенный модуль на 3, а не полагаться на общий алгоритм %; но вы не можете побить O(n), поскольку вам нужно сканировать каждый элемент хотя бы один раз, и решение уже не делает больше. (на самом деле, как вы просили написать результат, мне кажется, вы не можете сделать это менее чем O(n^2) только из-за этого ...)

Ни один из этих вопросов не имеет ничего общего с python. Знаете ли вы, что есть math.stackexchange.com?

Answer 2

Я перевожу код C ...

using namespace std; 
int main(){ 

    int n; 
    int k; 
    cin >> n >> k; 
    int a[n]; 
    int m[k]; 
    for(int i=0; i<k; i++) 
     m[i]=0; 
    for(int i = 0; i < n; i++){ 
     cin >> a[i]; 
     m[a[i]%k]++; 
    } 
    int sum=0; 
    sum+=(m[0]*(m[0]-1))/2; 
    for(int i=1; i<=k/2 && i!=k-i; i++){ 
     sum+=m[i]*m[k-i]; 
    } 
    if(k%2==0) 
     sum+=(m[k/2]*(m[k/2]-1))/2; 
    cout<<sum; 
    return 0; 
} 

в Python:

def divisible_sum_pairs(n, k, a_list): 
    m = [0] * len(a_list) 
    for a in a_list: 
     m[a % k] += 1 

    sum = int(m[0] * (m[0] - 1)/2) 
    for i in range(1, int(k/2) + 1): 
     if i != k - 1: 
      sum += m[i] * m[k - i] 
    if k % 2 == 0: 
     sum += m[int(k/2)] * (m[int(k/2)] - 1)/2 

    return sum 

С:

print(divisible_sum_pairs(6, 3, [1, 3, 2, 6, 1, 2])) 

Вы получаете 5