주어진 숫자로 나누어 진 배열의 부분 배열 수를 찾으십시오

Question

하나의 알고리즘 질문에 갇혀 있습니다. 아래의 문제에 대한 효율적인 알고리즘을 제안 해주십시오.

질문 합 주어진 숫자로 나누어 하위 어레이의

찾기 번호입니다.

I 복잡성이다 O 한 알고리즘 (N^2) 배열, 여기서, N = 크기가 만든

직장 내.

내 코드 주어진 수 X를 들어

#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; 
} 

Answer 1

...

기본 개념 :

하는 경우 (정확성의 비공식적 증명) 숫자의 합 [a, b] 범위는 X으로 나눌 수 있습니다.

적은 수학적 관점에서

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % 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 

그래서 : 오른쪽에 그 금액이 모두 X로 나눈 같은 나머지가있는 경우

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으로 나눌 수 있습니다. 정교 :

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 

이제 우리는 0 <= Q, S < X으로 일부 정수 P, Q, R 및 S에 대한 양식 RX + S에 양식 PX + Q 및 A에 B을 변환 할 수 있습니다. 여기서, 정의에 의해, 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은 (결과가 단순히 (P-R)입니다) X로 나눌 수 있습니다. 이제 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으로 다시 쓸 수 있습니다.

은 3으로 나눌 수 있습니다.

높은 수준의 접근 방식 :

각 값은 배열의 처음부터 시작까지 추가 일부 지정된 위치에 끝낼 수있는 방법을 여러 가지 방법으로 표현 key -> value의 해시 맵을 구축 sum mod X = key (아래 예에서 "Mod 3"라인 및 맵 값 참조).

지금, 위의 논리에 따라, 우리는 두 개의 하위 어레이는 처음부터 시작하여 모두 같은 sum mod X을 가진 각각의 위치 a 및 b에서 끝나는 경우, 부분 배열 [a, b]가 X으로 나눌 수 것이라는 점을 알고있다.

따라서 해시지도의 각 값은 가능한 시작 및 끝점 집합의 크기를 나타내며 X으로 나눌 수있는 부분 배열을 제공합니다 (모든 점은 시작 또는 끝 점이 될 수 있음).

시작 지점과 종료 지점을 선택할 수있는 방법의 수는 단순히
value choose 2 = value!/(2*(value-2)!) (값이 1이면 0)입니다.

따라서 해시 맵의 각 값에 대해 계산하여 모두를 더해서 X으로 나눌 수있는 하위 배열 수를 얻습니다.

알고리즘 :

지금까지 mod X 그 나머지 값이 표시되는 빈도의 수에 매핑 된 모든 숫자의 누적 합계를 저장하는 해시 맵을 구축는 (예상 O(n)으로 구성).

0의 값을 1 씩 늘립니다.이 값은 배열의 시작에 해당합니다.

카운트에 value!/(2*(value-2)!) 추가 해시 맵의 각 값에 대해 0

에 카운트를 초기화한다.

숫자가 원하는 값입니다.

실행 시간 :

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 
    1 -> 2 
    2 -> 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 

Answer 2

내가 쉽게 솔루션을 가질 수있다. O (n) 시간 및 O (n + k) 공간. 여기서 n은 배열의 크기입니다. & k는 우리가 나누기를 검사하는 숫자입니다.

는 A [N] 등의 배열을 고려 수가 K

1. 다른 배열 SUM_TILL_NOW [N]을 생성한다. 각 A [i] 채우기 SUM_TILL_NOW [i] = SUM_TILL_NOW [i-1] + A [i] % K에 대해
2. ; (SUM_TILL_NOW [0] = A [0])
3. 이 새로운 배열에서 두 개의 숫자를 찾습니다.

는이 SUM_TILL_NOW 어레이 위에 새로운 배열 CHECK [] 크기 K.

반복 처리를 만들고 체크 [SUM_TILL_NOW는 [내가] 설정되었는지 확인 수행.

i로 설정하지 않은 경우

다른 검사 [SUM_TILL_NOW은 [I], 나 합 이하 동일의 C++ 함수

K.

로 나누어 서브 세트이다.

#include <iostream> 
#include <string.h> 

using namespace std; 

void printrange(int* A, int N, int K) 
{ 
    int STN[N], C[K]; 
    memset(C, -1, K*sizeof(int)); 
    int i; 
    int sum=A[0]; 
    STN[0]= (A[0]%K); 
    for (i= 1; i< N; i++) 
    { 
     sum+= A[i]; 
     STN[i]= sum%K; 
    } 
    for(i=0; i< N; i++) 
    { 
     if(C[STN[i]] == -1) 
      C[STN[i]] =i; 
     else 
     { 
      cout<< C[STN[i]]+1 <<" "<< i; 
      break; 
     } 
    } 
} 

int main() 
{ 
    int A[]= {6, 9, 2, 1, 8, 6, 2, 5}; 
    printrange(A, sizeof(A)/sizeof(A[0]), 7); 
    return 0; 
}