Найти номера подмассива массива, сумма которых делится на заданное число

Для заданного числа X...

Основная идея: (с неофициальным подтверждением правильности)

Если сумма чисел в диапазоне [a, b] делится на X, то:

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X

В менее математических терминах:

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

So:

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

Затем, если эти суммы справа имеют одинаковый остаток при делении на X, остатки сокращаются, и сумма элементов между ними будет делиться на X. Разработка:

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

Теперь мы можем преобразовать B в форму PX + Q и A в форму RX + S для некоторых целых чисел P, Q, R и S с 0 <= Q, S < X. Здесь, по определению, Q и S будут соответствующими остатками от B и A при делении на X.

Тогда у нас есть:

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

Ясно, что (P-R)X делится на X (результат просто (P-R)). Теперь нам просто нужно, чтобы Q - S делилось на X, но, поскольку 0 <= Q, S < X, они должны быть равны.

Пример:

Пусть B = 13, A = 7, X = 3.

Здесь B % X = 1 и A % X = 1.

Мы можем переписать B как 4*3 + 1, а A как 2*3 + 1.

Затем C = 4*3 + 1 - 2*3 - 1 = 2*3, которое делится на 3.

Подход высокого уровня:

Постройте хэш-карту key -> value, где каждое значение представляет, сколько способов вы можете начать с начала массива и закончить в некоторой заданной позиции, что в сумме дает sum mod X = key (см. строку «Mod 3» и значения карты в пример ниже).

Теперь, основываясь на приведенной выше логике, мы знаем, что если два подмассива, начиная с начала и заканчивая позициями a и b соответственно, имеют одинаковые sum mod X, то подмассив [a, b] будет делиться на X.

Таким образом, каждое значение в хэш-карте представляет собой размер набора возможных начальных и конечных точек, что даст нам подмассив, кратный X (любая точка может быть как начальной, так и конечной точкой).

Количество возможных способов выбора этих начальных и конечных точек равно просто
value choose 2 = value!/(2*(value-2)!) (или 0 если значение равно 1).

Итак, мы вычисляем это для каждого значения в хэш-карте и складываем их все, чтобы получить количество подмассивов, кратное X.

Алгоритм:

Создайте хэш-карту, в которой будет храниться кумулятивная сумма всех чисел, mod X сопоставляемых на данный момент со счетчиком того, как часто появляется это остаточное значение (построено в ожидаемом O(n)).

Увеличьте значение 0 на единицу - это соответствует началу массива.

Инициализируйте счетчик равным 0.

Для каждого значения в хэш-карте добавьте value!/(2*(value-2)!) к счету.

Количество искомое значение.

Время работы:

Ожидается O(n).

Пример:

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

Подмассивы будут:

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

У меня может быть более простое решение. за время O(n) и пространство O(n+k). где n — размер массива, а k — число, с которым мы проверяем делимость.

Рассмотрим массив как A [n], а число равно K

1. создайте еще один массив SUM_TILL_NOW[n].
2. для каждого A[i] заполните SUM_TILL_NOW [i]= SUM_TILL_NOW[i-1]+A[i] %K; (СУММ_ДО_СЕЙЧАС[0]= А[0])
3. найти два числа, которые равны в этом новом массиве.

Для этого создайте новый массив CHECK[] размера K.

Переберите массив SUM_TILL_NOW и проверьте, установлен ли CHECK[SUM_TILL_NOW[i]].

Если не установить его на i.

иначе CHECK[SUM_TILL_NOW[i]], i — это подмножество, в котором сумма делится на K.

Ниже приведена аналогичная функция С++.

#include <iostream>
#include <string.h>

using namespace std;

void printrange(int* A, int N, int K)
{
    int STN[N], C[K];
    memset(C, -1, K*sizeof(int));
    int i;
    int sum=A[0];
    STN[0]= (A[0]%K);
    for (i= 1; i< N; i++)
    {
        sum+= A[i];
        STN[i]= sum%K;
    }
    for(i=0; i< N; i++)
    {
        if(C[STN[i]] == -1)
            C[STN[i]] =i;
        else
        {
            cout<< C[STN[i]]+1 <<" "<< i;
            break;
        }
    }
}

int main()
{
    int A[]= {6, 9, 2, 1, 8, 6, 2, 5};
    printrange(A, sizeof(A)/sizeof(A[0]), 7);
    return 0;
}