Количество подмассивов, делящихся на k - программирование
Подтвердить что ты не робот

Количество подмассивов, делящихся на k

У меня был следующий вопрос в интервью, и, несмотря на то, что я дал рабочую реализацию, это было недостаточно эффективно.

Ломкой массива A является любая пара целых чисел (P, Q) такая, что 0 ≤ P ≤ Q < N. Срез (P, Q) массива A делится на K, если число A [P] + A [P + 1] +... + A [Q-1] + A [Q] делится на K.

Функция, которую я попросил написать, должен был вернуть число делимых делителей на К. Ожидаемая сложность времени была O (max (N, K)), а сложность пространства была O (K).

Мое решение было самым простым, одним циклом внутри другого и проверить каждый срез: O (n ^ 2)

Я думал, но я действительно не могу понять, как это сделать в O (max (N, K)).

Это может быть вариант проблемы с подмножеством , но я не знаю, как подсчитывать каждый подмассив.

EDIT: Элементы в массиве могут быть отрицательными. Вот пример:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}
4b9b3361

ОТВЕТЫ

Ответ 1

Поскольку вас интересуют только числа, делимые на K, вы можете выполнять все вычисления по модулю K. Рассмотрите массив накопленных сумм S, такой что S[i] = S[0] + S[1] +... + S[i], Тогда (P, Q) является ломтиком, делимым на K, если S[P] = S[Q] (помните, что мы делаем все вычисления по модулю K). Таким образом, вы просто должны посчитать для каждого возможного значения [0,..., K-1], сколько раз оно появляется в S.

Вот некоторый псевдокод:

B = new array( K )
B[0]++
s = 0
for i = 0 to N - 1
  s = ( s + A[i] ) % K
  B[s]++
ans = 0
for i = 0 to K - 1
  ans = ans + B[i] * ( B[i] - 1 ) / 2

Как только вы узнаете, что это x ячеек в S, которые имеют значение i, вы захотите посчитать количество срезов, начинающихся в ячейке со значением я и заканчивающихся в ячейке со значением i, это число равно x ( x - 1 )/2 Чтобы решить краевые задачи, мы добавляем одну ячейку со значением 0.

Что означает x ( x - 1 )/2: Предположим, что наш массив равен [4, 5, 0], а частота 4 в качестве суммы префикса равна x, что в данном случае равно 3. Теперь мы можем сделать вывод из значения x, что есть, по крайней мере, числа x-1, которые либо делятся на k, либо имеют mod k, равный 0. Теперь общее число возможных подмассивов из этих чисел x-1 составляет 1 + 2 + 3... + (x - 1), который равен ( ( x - 1 ) * ( ( x - 1 ) + 1 )/2 (Стандартная формула для суммирования от 1 до N, где N обозначает (x - 1).

Ответ 2

Для заданного числа 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

Итак:

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.

Высокоуровневый подход:

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

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

Инициализировать счетчик до 0.

Пройдите через хэш-карту и добавьте (= value!/(2*(value-2)!)) к счету. 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
  2 -> 2
  1 -> 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

Ответ 3

    private int GetSubArraysCount(int[] A, int K)
    {
        int N = A.Length;
        int[] B = new int[K];
        for (int i = 0; i < B.Length; i++)
        {
            B[i] = 0;
        }
        B[0]++;
        int s = 0;
        for (int i = 0; i < N; i++)
        {
            s = (s + A[i]) % K;
            while (s < 0)
            {
                s += K;
            }
            B[s]++;
        }
        int ans = 0;
        for (int i = 0; i <= K - 1; i++)
        {
            ans += B[i] * (B[i] - 1) / 2;
        }
        return ans;
    }

Ответ 4

static void Main(string[] args)
    {
        int[] A = new int[] { 4, 5, 0, -2, -3, 1 };
        int sum = 0;
        int i, j;
        int count = 0;
        for (i = 0; i < A.Length; i++)
        {
            for (j = 0; j < A.Length; j++)
            {
                if (j + i < 6)
                    sum += A[j + i];
                if ((sum % 5) == 0)
                    count++;

            }
            sum = 0;
        }
        Console.WriteLine(count);
        Console.ReadLine();


    }

Ответ 5

Вот реализация Java решения, предложенного @Thomash.

Второй цикл не нужен, потому что мы можем напрямую увеличить ответ на текущее значение и затем увеличить его.

Чтобы избежать отрицательного индекса массива, нам также нужно настроить вычисление модуля.

public static int countSubarrays(int[] nums, int k) {
    int[] cache = new int[k];
    cache[0]++;
    int s = 0, counter = 0;
    for (int i = 0; i < nums.length; i++) {
        s = ((s + nums[i]) % k + k) % k;
        counter += cache[s];
        cache[s]++;
    }

    return counter;
}

Ответ 6

Пример: -

Входной массив

int [] nums = {4,3,1,2,1,5,2};

K равно 3

Последовательная сумма

4,7,8,10,11,16,18

Разделите над последовательным массивом сумм на 3

1,1,2,1,2,1,0

так что у нас есть четыре 1, два 2, один 0

поэтому общий счет будет (4 * 3)/2 + (2 * 1)/2 + (2 * 1)/2 = 8

(4 * 3)/2 происходит от выбора любых двух 1 из четырех, т.е. nC2 = n (n-1)/2

Вот программа

public static long countSubArrayDivByK (int k, int [] nums) {

    Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
    int [] consecSum = new int[nums.length];
    consecSum[0]=nums[0];

    for(int i=1;i<nums.length;i++){
        consecSum[i]= consecSum[i-1] +nums[i];
    }

    for(int i=0;i<nums.length;i++){
        consecSum[i]= consecSum[i]%k;

            if(consecSum[i]==0 && modulusCountMap.get(consecSum[i])==null){
                modulusCountMap.put(consecSum[i], 2);
            }else{
                modulusCountMap.put(consecSum[i], modulusCountMap.get(consecSum[i])==null ? 1 : modulusCountMap.get(consecSum[i])+1);
            }

    }

    int count = 0;

    for (Integer val : modulusCountMap.values()) {
        count = count +  (val*(val-1))/2;
    }

    return count;
}

Оптимизированная версия выше

static long customOptimizedCountSubArrayDivByK(int k, int[] nums) {

        Map<Integer, Integer> modulusCountMap = new HashMap<Integer, Integer>();
        int [] quotient = new int[nums.length];
        quotient[0]=nums[0]%3;



        if(quotient[0]==0){
            modulusCountMap.put(quotient[0], 2);
        }else{
            modulusCountMap.put(quotient[0], 1);
        }


        for(int i=1;i<nums.length;i++){
            quotient[i]= (quotient[i-1] + nums[i])%3;


                if(quotient[i]==0 && modulusCountMap.get(quotient[i])==null){
                    modulusCountMap.put(quotient[i], 2);
                }else{
                    modulusCountMap.put(quotient[i], modulusCountMap.get(quotient[i])==null ? 1 : modulusCountMap.get(quotient[i])+1);
                }

        }

        int count = 0;

        for (Integer val : modulusCountMap.values()) {
            count = count +  (val*(val-1))/2;
        }

        return count;
    }

Ответ 7

Спасибо за ваше решение, @damluar, это очень аккуратно! Я просто хочу добавить некоторые комментарии.

  • Результат должен быть 7, а не 6 в качестве вывода. Поскольку у нас есть 7 подмассивов, которые делятся на k, как показано ниже, добавив res += storedArray[0];, чтобы исправить это.

{4, 5, 0, -2, -3, 1}; {5}; {5, 0}; {5, 0, -2, -3}; {0}; {0, -2, -3}; {-2, -3}

Ссылка ссылки

  1. Инициализация cache[0]++; зависит от языка, если он использует С++, он нужен, но это необязательно для java [ссылка].

код:

public class HelloWorld{

public static void main(String []args){
    int [] A = new int[] {4,5,0,-2,-3,1};
    int k = 5;
    int ans=0;
    System.out.println(countSubArray(A, k)); // output = 7

}

public static int countSubArray(int [] nums, int k){
    int [] storedArray = new int[k];
    int sum=0, res=0;
    for(int i=0; i<nums.length; i++){
        sum = (((sum + nums[i]) % k) + k) % k;
        res += storedArray[sum];
        storedArray[sum]++;

    }
    res += storedArray[0];
    return res; 
}
}

Ответ 8

public class SubArrayDivisible 
{

    public static void main(String[] args) 
    {
        int[] A = {4, 5, 0, -2, -3, 1};
        SubArrayDivisible obj = new SubArrayDivisible();
        obj.getSubArrays(A,5);
    }

    private void getSubArrays(int[] A,int K)
    {
        int count = 0,s=0;
        for(int i=0;i<A.length;i++)
        {
            s = 0;
            for(int j = i;j<A.length;j++)
            {
                s = s+A[j];
                if((s%K) == 0)
                {
                    System.out.println("Value of S "+s);
                    count++;
                }

            }
        }
        System.out.println("Num of Sub-Array "+count);
    }
}