子阵整除k的数 [英] Number of subarrays divisible by k

问题描述

我曾在一次采访中以下问题和，尽管我给一个工作实施这一事实，它是不够高效。

  

数组A的切片是任何整数对（P，Q），使得0≤P≤Q   ＆LT;数组A的N.切片（P，Q）是整除k如果数A [P] +   A [P + 1] + ... + A [Q-1] + A [Q]整除被K。

功能我被要求写，不得不返回片由K.整除预期的时间复杂度为O（MAX（N，K））和数字空间复杂度为O（K）。

我的解决方案是最简单的，一个循环在另一个和检查每一个片：为O（n ^ 2）

我一直在想，但我真的想不通我怎么能做到这一点在O（MAX（N，K））。

这可能是子集和问题的一个变种，但我不知道怎么算每个子数组。

编辑：在数组中的元素可能是负面影响。下面是一个例子：

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

函数必须返回7，因为有7子阵哪些款项是整除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中。

下面是一些伪code：

  B =新阵列（K）
B [0] ++
S = 0
对于i = 0至N-1
  S =（S + A [1]）％K
  B〔S] ++
ANS = 0
对于i = 0到K-1的
  答+ = B [i]于*（乙[Ⅰ] -1）/ 2
 

一旦你知道它们是x细胞的S有我的价值，你要计算的片数的开始与值I细胞，结束与价值我一个细胞，这个数字是X（X- 1）/ 2。为了解决边缘问题，我们添加一个单元格值为0。

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 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.

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).

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

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.

EDIT: 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}

解决方案

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.

Here is some pseudocode:

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 += B[i]*(B[i]-1)/2

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.

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