배열 arr[]와 정수 k가 입력으로 주어집니다. 목표는 해당 하위 배열 요소의 곱이 k로 나눌 수 있도록 arr[]의 하위 배열 수를 찾는 것입니다.
예를 들어
입력
arr[] = {2, 1, 5, 8} k=4 출력
Count of sub-arrays whose product is divisible by k are: 4
설명
The subarrays will be: [ 8 ], [ 5,8 ], [ 1,5,8 ], [ 2,1,5,8 ].
입력
arr[] = {7,1,9,7} k=9 출력
Count of sub−arrays whose product is divisible by k are: 6
설명
The subarrays will be: [ 9 ], [ 9,7 ], [ 1,9 ], [ 1,9,7 ], [ 7,1,9 ], [ 7,1,9,7 ].
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
순진한 접근 방식
우리는 두 가지 접근 방식을 사용하여 이 문제를 해결할 것입니다. 순진한 접근 방식에서는 두 개의 for 루프를 사용하여 배열을 순회하고 인덱스 i와 j 사이의 각 하위 배열에 대해 요소의 곱이 k로 나눌 수 있는지 확인합니다. 그렇다면 카운트를 증가시키십시오.
-
정수 배열 arr[] 및 k를 입력으로 사용합니다.
-
함수 product_k(int arr[], int size, int k)는 배열과 k를 취하고 곱이 k로 나눌 수 있는 하위 배열의 개수를 반환합니다.
-
초기 카운트를 입력으로 사용합니다.
-
i=0에서 i<크기로, j=i에서 j<크기로 arr을 트래버스합니다. 그리고 k=i ~ k<=j
-
각 하위 배열 arr[ i ~ j ]에 대해 arr[k]를 temp에 곱합니다.
-
제품 온도가 k로 나눌 수 있으면 카운트를 증가시킵니다.
-
세 개의 루프가 모두 끝나면 count를 결과로 반환합니다.
효율적인 접근
W 이 접근 방식에서는 각 하위 배열을 순회하는 대신 제품을 세그먼트 트리에 저장합니다. 이제 k로 나눌 수 있는 이 트리의 곱을 사용합니다. 그에 따라 카운트를 증가시킵니다.
-
정수 배열 arr[] 및 k를 입력으로 사용합니다.
-
세그먼트 트리를 배열 arr_2[4 * size_2]로 구현합니다.
-
함수 set_in(int fit, int first, int last, const int*rr, int k)는 제품에 대한 세그먼트 트리를 작성하는 데 사용됩니다.
-
함수 검사(int fit, int first, int last, int start, int end, int k)는 시작과 끝 사이의 하위 배열의 곱을 찾는 데 사용됩니다.
-
첫 번째>마지막 또는 첫 번째>종료 또는 마지막인 경우<시작은 1을 반환합니다.
-
first>=last 및 last<=end이면 arr_2[fir]%k를 반환합니다.
-
level=first+last>> 1을 설정합니다(2로 나누기).
-
이제 레벨 및 레벨+1에 대한 재귀 호출 check()를 호출하고 set_1 및 set_2에 저장합니다.
-
count=set_1+set_2를 설정하고 count를 반환합니다.
-
함수 product_k(int arr[], int size, int k)는 arr[]와 k를 취하고 곱이 k로 나누어 떨어지는 부분 배열의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
초기 카운트를 0으로 설정합니다.
-
i=0에서 i
-
이 온도가 0이면 카운트를 증가시킵니다.
-
최종 결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int product_k(int arr[], int size, int k){
int count = 0;
for (int i = 0; i < size; i++){
for (int j = i; j < size; j++){
int temp = 1;
for (int k = i; k <= j; k++){
temp = temp * arr[k];
}
if(temp % k == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {2, 1, 5, 8, 10, 12 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of sub−arrays whose product is divisible by k are: 18
예시(효율적인 접근)
#include <bits/stdc++.h>
using namespace std;
#define size_2 100002
int arr_2[4 * size_2];
void set_in(int fit, int first, int last, const int* arr, int k){
if (first == last){
arr_2[fit] = (1LL * arr[first]) % k;
return;
}
int level = (first + last) >> 1;
set_in(2 * fit, first, level, arr, k);
set_in(2 * fit + 1, level + 1, last, arr, k);
arr_2[fit] = (arr_2[2 * fit] * arr_2[2 * fit + 1]) % k;
}
int check(int fit, int first, int last, int start, int end, int k){
if(first > last){
return 1;
}
if(first > end){
return 1;
}
if(last < start){
return 1;
}
if (first >= start){
if(last <= end){
return arr_2[fit] % k;
}
}
int level = (first + last) >> 1;
int set_1 = check(2 * fit, first, level, start, end, k);
int set_2 = check(2 * fit + 1, level + 1, last, start, end, k);
int count = (set_1 * set_2) % k;
return count;
}
int product_k(int arr[], int size, int k){
int count = 0;
for (int i = 0; i < size; i++){
for (int j = i; j < size; j++){
int temp = check(1, 0, size − 1, i, j, k);
if (temp == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {2, 1, 5, 8, 10, 12};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
set_in(1, 0, size − 1, arr, k);
cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of sub−arrays whose product is divisible by k are: 18