정수 유형 요소의 배열이 주어지고 주어진 배열에서 쌍을 형성하고 쌍에 있는 요소의 합을 계산하고 주어진 합이 k로 나눌 수 있는지 여부를 확인하는 작업입니다.
입력 - 정수 arr[] ={4, 1, 2, 0, 2}, 정수 k =2
출력 − 합이 k로 나누어지는 배열의 카운트 쌍은 − 2
입니다.설명 − 주어진 배열에서 형성할 수 있는 쌍은 다음과 같습니다. (4, 1) =5(2로 나눌 수 없음), (4, 2) =6(2로 나눌 수 있음), (4, 0) =4( 2), (1, 2) =3(2로 나눌 수 없음), (1, 0) =1(2로 나눌 수 없음), (2, 0) =2(2로 나눌 수 없음), (2, 2) =4(2의 배수), (0, 2) =2(2의 배수). 따라서 k로 나눌 수 있는 합을 2로 하는 쌍은 (4, 2), (4, 0), (2, 0), (2, 2) 및 (0, 2)입니다.
입력 - 정수 arr[] ={2, 4, 8, 6, 10}, 정수 k =4
출력 − 합이 k로 나누어지는 배열의 카운트 쌍은 − 4입니다.
설명 - 주어진 배열에서 만들 수 있는 쌍은 다음과 같습니다. (2, 4) =6(4로 나눌 수 없음), (2, 8) =10(4로 나눌 수 없음), (2, 6) =8(나누기 4), (2, 10) =12(4로 나눌 수 있음), (4, 8) =12(4로 나눌 수 있음), (4, 6) =10(4로 나눌 수 없음), (4, 10) =14(4로 나누어 떨어지지 않음), (8, 6) =14(4로 나누어 떨어지지 않음), (8, 10) =18(4로 나누어 떨어지지 않음), (6, 10) =16(4로 나누어 떨어지지 않음). 따라서 합이 4로 나누어 떨어지는 쌍은 (2, 10), (2, 6), (4, 8) 및 (6, 10)입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
주어진 문제를 해결하기 위한 여러 가지 접근 방식, 즉 순진한 접근 방식과 효율적인 접근 방식이 있을 수 있습니다. 먼저 순진한 접근 방식을 살펴보겠습니다. .
-
정수 요소의 배열과 정수 변수를 k로 입력한 다음 배열의 크기를 계산하고 데이터를 함수에 전달
-
k로 나눌 수 있는 합으로 쌍의 수를 저장하는 임시 변수 count를 선언합니다.
-
배열의 크기까지 i에서 0까지 FOR 루프 시작
-
루프 내에서 배열의 크기까지 j에서 i + 1까지 FOR 또 다른 루프를 시작합니다.
-
루프 내에서 합계를 arr[i] + arr[j]로 계산하고 IF sum % k ==0을 확인한 다음 카운트를 1씩 증가시킵니다.
-
개수 반환
-
결과를 인쇄합니다.
효율적인 접근
-
정수 요소의 배열을 입력하고 배열의 크기를 계산하고 데이터를 함수에 전달
-
k로 나눌 수 있는 합으로 쌍의 수를 저장하는 임시 변수 count를 선언합니다.
-
k로 나눌 수 있는지 확인해야 하므로 k 크기의 배열을 만듭니다.
-
배열의 크기까지 i에서 0까지 FOR 루프 시작
-
루프 내에서 temp를 arr[i] % k로 설정하고 배열을 ++check[temp]
로 사전 증가시킵니다. -
카운트를 new_arr[0] * (new_arr[0] - 1)/2
로 설정 -
i <=k/2 AND i !=(k-i)
까지 루프 FOR를 i에서 1로 시작합니다. -
루프 내에서 count를 count + new_arr[i] * (new_arr[k - i])
로 설정합니다. -
IF k % 2 =0을 확인한 다음 count를 count + (new_arr[k / 2] * (new_arr[k / 2] - 1) / 2)
로 설정합니다. -
개수 반환
-
결과를 인쇄하십시오.
예(순진한 접근 방식)
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int count = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
int sum = arr[i] + arr[j];
if(sum % k == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count pairs in array whose sum is divisible by k are: 6
예시(효율적인 접근)
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int temp = 0;
int count = 0;
int check[k] = {0};
for (int i = 0; i < size; i++){
temp = arr[i] % k;
++check[temp];
}
count = check[0] * (check[0] - 1) / 2;
for (int i = 1; i <= k / 2 && i != (k - i); i++){
count = count + check[i] * (check[k - i]);
}
if (k % 2 == 0){
count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count pairs in array whose sum is divisible by k are: 6