문제 설명
주어진 배열 "arr"에서 작업은 배열을 양호하게 만들기 위해 제거할 요소의 최소 수를 찾는 것입니다.
시퀀스 a1, a2, a3. . .an은 각 요소 a[i]에 대해 a[i] + a[j]가 2의 거듭제곱이 되도록 요소 a[j](i는 j와 같지 않음)가 존재하는 경우 양호라고 합니다.
arr1[] = {1, 1, 7, 1, 5}
위의 배열에서 요소 '5'를 삭제하면 배열이 좋은 배열이 됩니다. 이 후 arr[i] + arr[j]의 쌍은 2의 거듭제곱 -
입니다.- arr[0] + arr[1] =(1 + 1) =2의 2승
- arr[0] + arr[2] =(1 + 7) =2의 거듭제곱인 8
알고리즘
1. We have to delete only such a[i] for which there is no a[j] such that a[i] + a[i] is a power of 2. 2. For each value find the number of its occurrences in the array 3. Check that a[i] doesn’t have a pair a[j]
예시
#include <iostream> #include <map> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int minDeleteRequred(int *arr, int n){ map<int, int> frequency; for (int i = 0; i < n; ++i) { frequency[arr[i]]++; } int delCnt = 0; for (int i = 0; i < n; ++i) { bool doNotRemove = false; for (int j = 0; j < 31; ++j) { int pair = (1 << j) - arr[i]; if (frequency.count(pair) && (frequency[pair] > 1 || (frequency[pair] == 1 && pair != arr[i]))) { doNotRemove = true; break; } } if (!doNotRemove) { ++delCnt; } } return delCnt; } int main(){ int arr[] = {1, 1, 7, 1, 5}; cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl; return 0; }
출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Minimum elements to be deleted = 1