Đề bài
Cho một mảng "arr", nhiệm vụ là tìm số lượng phần tử tối thiểu cần xóa để mảng trở thành mảng "tốt".
Một dãy a1, a2, a3...an được gọi là tốt nếu với mỗi phần tử a[i], tồn tại một phần tử a[j] (i khác j) sao cho a[i] + a[j] là lũy thừa của hai.
arr1[] = {1, 1, 7, 1, 5}
Trong mảng trên nếu xóa phần tử '5' thì mảng trở thành mảng tốt. Sau đó bất kỳ cặp arr[i] + arr[j] nào đều là lũy thừa của hai:
- arr[0] + arr[1] = (1 + 1) = 2 là lũy thừa của hai
- arr[0] + arr[2] = (1 + 7) = 8 là lũy thừa của hai
Thuật toán
1. Chúng ta chỉ phải xóa những a[i] mà không có a[j] sao cho a[i] + a[i] là lũy thừa của 2. 2. Với mỗi giá trị tìm số lần xuất hiện của nó trong mảng 3. Kiểm tra a[i] không có cặp a[j]
Ví dụ
#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; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum elements to be deleted = 1