找到一个数组，其总和由给定数量除以子阵数量 [英] Find numbers of subarray of an array whose sum is divided by given number
问题描述
我被困在一个算法问题。请建议我一些有效的算法，下面的问题。
的问题是
查找子阵列，其总和整除定数的数字。
我的工作
我做了一个算法，其复杂度为O（N ^ 2），这里，N =大小的数组。
我的code
＃包括＆LT; stdio.h中＆GT;
使用名字空间std;
主要（） {
INT N;
INT磷;
INT笔;
INT VAL;
长长的诠释计数= 0;
得到long long int答案= 0;
scanf函数（％d个，＆amp; T公司）;
// T = 20;
对于（INT K = 1; K＆LT; = T; k ++）{
scanf函数（％d个，和放大器; N）;
scanf函数（％D，与安培; P）;
计数= 0;
答案= 0;
的for（int i = 0; I＆n种;我++）{
scanf函数（％d个，和放大器; VAL）;
数+ = VAL;
workingArray [我] =计数;
}
对于（INT长度= 1;长度＆LT; = N，长度++）{
对于（INT开始= 0;启动＆LT; =（N-长度）;启动++）{
如果（开始== 0）{
如果（workingArray [启动+长度为1]％P == 0）回答++;
}
否则，如果（（workingArray [启动+长度-1] - workingArray [开始-1）％P == 0）回答++;
}
}
的printf（案例＃％D \ N％LLD \ N，K，答案）;
}
返回0;
}
对于一个给定数量 X ...
的基本思路：（与正确性的正规证明）
如果该数字在范围之 [A，B] 是整除 X ，则：
（Σ<子> i = 1到A-1 输入[I]）％X =（Σ<子> I = 1至B 输入[我]）％X
在少数学方面：
从第一个元素的总和B =总和从第一个元素到
+两者之间的元素的总和
所以：
的两者之间的元素的总和=从第一个元素的总和为b
- 从第一个元素的总和为
然后，如果在右侧那些总和都具有当由 X 除以相同余数，该余数将抵消和两者之间的元件的总和将整除通过 X 。详细阐述：
的 C =两者之间的元素的总和
B =从第一个元素的总和为b
A =在从第一个元素到一个总和
现在，我们可以把 B 的形式 PX + Q 和 A 的形式 RX + S ，对于一些整数 P ，问： ，研究和取值，与 0℃= Q S＆LT; X 。在这里，顾名思义，问：和取值是 B各自的余数和 A 除以 X 。
然后我们有：
C =（PX + Q） - （RX + S）
C = PX + Q - RX - S
C = PX - RX + Q - S
C =（P-R）x + Q - S
显然（PR）X 是整除 X （结果是根本（ PR））。现在我们只需要问： - S 来除尽 X ，但是，因为 0℃ = Q，S＆LT; 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。
穿过散列映射，并添加价值选择2 （= 超值！/（2 *（价值2）！） ）来计数。该 2 我们选择这里的起点和子阵的结束位置。
的计数是所需的值。
运行时间：
预计 O（N）。
示例：
输入：0 5 3 8 2 1
X = 3
总和：0 0 5 8 16 18 19
模3：0 0 2 2 1 0 1
地图：
0 - ＆GT; 3
2 - ＆GT; 2
1 - ＆GT; 2
数= 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
I got stuck in one algorithm question. Please suggest me some efficient algorithm for the below problem.
Question is
Find numbers of subarrays whose sum is divisible by given number.
My work
I made one algorithm, whose complexity is O(N^2), here, N = size of an array.
My Code
#include<stdio.h>
using namespace std;
main() {
int N;
int P;
int T;
int val;
long long int count = 0;
long long int answer = 0;
scanf("%d", &T);
//T = 20;
for(int k = 1; k <= T; k++) {
scanf("%d", &N);
scanf("%d", &P);
count = 0;
answer = 0;
for(int i = 0; i < N; i++) {
scanf("%d", &val);
count += val;
workingArray[i] = count;
}
for(int length = 1; length <= N; length++) {
for(int start = 0; start <= (N-length); start++) {
if( start == 0 ) {
if(workingArray[start+length-1]%P == 0) answer++;
}
else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
}
}
printf("Case #%d\n%lld\n", k, answer);
}
return 0;
}
For a given number X...
The basic idea: (with informal proof of correctness)
If the sum of the numbers in the range [a, b] is divisible by X, then:
(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X
In less mathematical terms:
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
Then, if those sums on the right both have the same remainder when divided by X, the remainders will cancel out and sum of the elements between the two will be divisible by X. An elaboration:
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
Now we can convert B to the form PX + Q and A to the form RX + S, for some integers P, Q, R and S, with 0 <= Q, S < X. Here, by definition, Q and S would be the respective remainders of B and A being divided by X.
Then we have:
C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S
Clearly (P-R)X is divisible by X (the result is simply (P-R)). Now we just need Q - S to be divisible by X, but, since 0 <= Q, S < X, they'll need to be equal.
Example:
Let B = 13, A = 7, X = 3.
Here B % X = 1 and A % X = 1.
We can rewrite B as 4*3 + 1 and A as 2*3 + 1.
Then C = 4*3 + 1 - 2*3 - 1 = 2*3, which is divisible by 3.
High-level approach:
Construct a hash-map which will store the cumulative sum of all the numbers thus far mod X mapped to the count of how often that remainder value appears (constructed in expected O(n)).
Increase 0's value by one - this corresponds to the start of the array.
Initialize a count to 0.
Go through the hash-map and add value choose 2 (= value!/(2*(value-2)!)) to the count. The 2 we're choosing here are the starting and ending positions of the subarray.
The count is the desired value.
Running time:
Expected O(n).
Example:
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
The subarrays will be:
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
这篇关于找到一个数组，其总和由给定数量除以子阵数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
