주어진 작업은 K로 나눌 수 있는 arr[i] + arr[j] 쌍의 최대 수를 계산하는 것입니다. 여기서 arr[]은 N개의 정수를 포함하는 배열입니다.
특정 인덱스 번호가 두 개 이상의 쌍에서 사용될 수 없다는 조건을 감안할 때.
입력
arr[]={1, 2 ,5 ,8 ,3 }, K=2 출력
2
설명 − 원하는 쌍은 다음과 같습니다. (0,2), (1,3) 1+5=6 및 2+8=10 . 6과 10은 모두 2의 배수입니다.
대안 답은 (0,4), (1,3) 또는 (2,4), (1,3) 쌍일 수 있지만 답은 동일하게 유지됩니다. 즉, 2입니다.
입력
arr[]={1 ,3 ,5 ,2 ,3 ,4 }, K=3 출력
3
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
int 유형의 변수 n에 배열의 크기를 저장
-
MaxPairs() 함수에서 정렬되지 않은 맵을 사용하고 배열의 각 요소에 대해 um[arr[i]%K] 값을 하나씩 증가시킵니다.
-
가능한 모든 um 값을 반복하고 가져옵니다.
-
um 값이 0이면 쌍의 수는 um[0]/2가 됩니다.
-
그런 다음 (um[a], um[Ka])
의 최소값을 사용하여 모든 um 값 'a'에서 쌍을 형성할 수 있습니다. -
um 값에서 사용된 쌍의 수를 뺍니다.
예시
#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i] % K]++;
}
int count = 0;
/*Iteration for all the number that are less than the hash value*/
for (auto it : um){
// If the number is 0
if (it.first == 0){
//Taking half since same number
count += it.second / 2;
if (it.first % 2 == 0){
um[it.first] = 0;
}
else{
um[it.first] = 1;
}
}
else{
int first = it.first;
int second = K - it.first;
// Check for minimal occurrence
if (um[first] < um[second]){
//Taking the minimal
count += um[first];
//Subtracting the used pairs
um[second] -= um[first];
um[first] = 0;
}
else if (um[first] > um[second]){
// Taking the minimal
count += um[second];
//Subtracting the used pairs
um[first] -= um[second];
um[second] = 0;
}
else{
//Checking if the numbers are same
if (first == second){
//If same then number of pairs will be half
count += it.second / 2;
//Checking for remaining
if (it.first % 2 == 0)
um[it.first] = 0;
else
um[it.first] = 1;
}
else{
//Storing the number of pairs
count += um[first];
um[first] = 0;
um[second] = 0;
}
}
}
}
return count;
}
//Main function
int main(){
int arr[] = { 3, 6, 7, 9, 4, 4, 10 };
int size = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<<"Maximize the number of sum pairs which are divisible by K is: "<<MaxPairs(arr, size, K);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과가 나옵니다. -
Maximize the number of sum pairs which are divisible by K is: 3