可被 k 整除的子数组数 [英] Number of subarrays divisible by k

问题描述

我在一次采访中遇到了以下问题，尽管我给出了一个可行的实现，但它的效率还不够高.

I had the following question in an interview and, in spite of the fact that I gave a working implementation, it wasn't efficient enough.

数组 A 的切片是任意一对整数 (P, Q) 使得 0 ≤ P ≤ Q<N.如果数 A[P] +A[P+1] + ... + A[Q−1] + A[Q] 可以被 K 整除.

A slice of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. A slice (P, Q) of array A is divisible by K if the number A[P] + A[P+1] + ... + A[Q−1] + A[Q] is divisible by K.

我被要求编写的函数必须返回可被 K 整除的切片数.预期的时间复杂度为 O(max(N, K))，空间复杂度为 O(K).

The function I was asked to write, had to return the number of slices divisible by K. The expected time complexity was O(max(N, K)) and space complexity was O(K).

我的解决方案是最简单的，一个循环在另一个循环中并检查每个切片:O(n^2)

My solution was the simplest, one loop inside another and check every slice: O(n^2)

我一直在想，但我真的不知道如何在 O(max(N, K)) 中做到这一点.

I have been thinking but I really can't figure out how can I do it in O(max(N, K)).

它可能是子集求和问题的变体，但我不知道如何计算每个子数组.

It may be a variant of the subset sum problem, but I don't know how to count every subarray.

数组中的元素可能是负数.下面是一个例子:

Elements in array could be negatives. Here is an example:

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}

推荐答案

由于您只对可被 K 整除的数感兴趣，因此您可以进行所有以 K 为模的计算.考虑累积和数组 S 使得 S[i] = S[0] + S[1] + ... + S[i].然后 (P, Q) 是一个可被 K 整除的切片，当条件是 S[P] = S[Q](记住我们所有的计算都是以 K 为模的).因此，您只需计算 [0 ,..., K-1] 的每个可能值在 S 中出现的次数.

As you are only interested in numbers divisible by K, you can do all computations modulo K. Consider the cumulative sum array S such that S[i] = S[0] + S[1] + ... + S[i]. Then (P, Q) is a slice divisible by K iff S[P] = S[Q] (remember we do all computations modulo K). So you just have to count for each possible value of [0 ,..., K-1] how many times it appears in 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

一旦您知道它们是 S 中具有值为 i 的 x 个单元格，您想计算从值为 i 的单元格开始到值为 i 的单元格结束的切片数，这个数字是 x( x - 1 )/2.为了解决边缘问题，我们添加了一个值为 0 的单元格.

Once you know that they are x cells in S that have value i, you want to count the number of slices the start in a cell with value i and ends in a cell with value i, this number is x ( x - 1 ) / 2. To solve edge problems, we add one cell with value 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 ).

What does x ( x - 1 ) / 2 stands for: Let's assume our array is [4, 5, 0] and frequency of 4 as prefix sum is x, which is 3 in this case. Now we can conclude from value of x, that there are at least x-1 numbers which are either divisible by k or have mod k equals to 0. Now total possible sub arrays out of these x-1 numbers are 1 + 2 + 3 ... + ( x - 1 ) which is ( ( x - 1 ) * ( ( x - 1 ) + 1 ) / 2 . (Standard formula for summation from 1 to N where N stands for ( x - 1 ).

这篇关于可被 k 整除的子数组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！