如何找到最长的连续子阵列，其总和的长度为整除给定数目 [英] how to find the length of the longest contiguous subarray whose sum is divisible by a given number

问题描述

我想找到的最长的连续子数组，其总和整除许多k'.I已经完成使用蛮力与复杂度为O（N ^ 2）它。但要做到这一点对O（N） 。可有人建议我解决了O（n）时间这一问题的有效途径。

I want to find the longest continuous sub array whose sum is divisible by a number 'k'.I have already done it using brute force with complexity o(n^2).But wants to do it for o(n).can anyone suggest me the efficient way to solve this problem in o(n) time.

有关，例如：     {1 3 1 3 6}

for eg: {1 3 1 3 6}

子阵的最大长度是被3整除的  2.即{3,6}

the max length of subarray which is divisible by 3 is 2. i.e {3,6}

另外需要注意的是k的这里的价值是非常大的约10 ^ 6，所以我不能使用，其中的每个元素的模被记录，因为它是有效的只有少数的preFIX数总和法。

Also to note that the value of k here is very large around 10^6 so I can not use the prefix sum method where in modulo of each element is recorded as it is valid for small numbers only.

这么好心给我建议，解决在C中这一问题的有效途径。

so kindly suggest me the efficient way to solve this problem in C.

推荐答案

下面是可以使用的一种方法：
创建求和模k的数组，例如。
让阵列：{} 3,4,10,15,1,4,7
和k = 5。然后，求和模阵列会是什么样子：
{3,2,2,2,3,2,4}被创建为：{3％5，（3 + 4）5％，（3 + 4 + 10）％5 ...}等。 现在发现的最大的折射率差的B / W类似的数字。由于k＆LT; = 10 ^ 6，你可以很容易地做到这一点使用数组的大小k的
。 在这种情况下，它可以是： - 或{（4-0 = 4）>指数3} {（5-1 = 4） - >索引的2}，因此4

Here is a way that can be used:
Create an array of summation-modulo k, eg.
Let the array be: {3,4,10,15,1,4,7}
and k = 5. Then, summation modulo array would look like:
{3,2,2,2,3,2,4} which is created as: {3%5, (3+4)%5, (3+4+10)%5... } and so on. Now find max index difference b/w similar numbers. Since k<=10^6, you can easily do this using array of size k.
In this case, it can be: {(4-0 = 4) ->index of 3} or {(5-1 = 4) ->index of 2}, so 4.

#include<stdio.h>
int main(){
    int n,k,i,j;
    scanf("%d%d",&n,&k);                    //size of the input array 'n' and modular 'k'
    int a[n];
    for(i = 0;i < n;i++)
            scanf("%d",&a[i]);

    //actual processing starts
    //creating summation modulo array in 'a' itself
    a[0] %= k;
    for(i = 1;i < n;i++){
            a[i] = (a[i-1] + a[i]) % k;
    }

    int r[2][k];
    for(i = 0;i < k;i++)
            r[0][i] = r[1][i] = -1;                 //initializing 'r' to -1
    //now evaluating min and max position of any spec no.
    for(i = 0;i < n;i++){
            if(r[0][a[i]] == -1)
                    r[0][a[i]] = i;
            else
                    r[1][a[i]] = i;
    }
    //evaluation of min-max indices complete

    int g = 0;
    //now find max diff if both values are set
    for(i = 0;i < k;i++){
            if(r[0][i] != -1 && r[1][i] != -1 && r[1][i] - r[0][i] > g)
                    g = r[1][i] - r[0][i];
    }
    printf("%d\n",g);               //this is the required answer
}

这篇关于如何找到最长的连续子阵列，其总和的长度为整除给定数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！