Cho mảng đại diện cấp số nhân thiếu một phần tử. Tìm phần tử thiếu. Ví dụ [1,3,27,81] → 9.
Dùng tìm kiếm nhị phân: kiểm tra tỷ số giữa phần tử giữa và phần tử kế tiếp, so sánh với tỷ số chung.
Ví dụ
#include <iostream> #include <cmath> using namespace std; class Progression { public: int missingUtil(int arr[], int left, int right, int ratio) { if (right <= left) return INT_MAX; int mid = left + (right - left) / 2; if (arr[mid + 1] - arr[mid] != ratio) return (arr[mid] * ratio); if (mid > 0 && arr[mid] / arr[mid - 1] != ratio) return (arr[mid - 1] * ratio); if (arr[mid] == arr[0] * pow(ratio, mid)) return missingUtil(arr, mid + 1, right, ratio); return missingUtil(arr, left, mid - 1, ratio); } int missingElement(int arr[], int n) { int ratio = pow(arr[n-1]/arr[0], 1.0/n); return missingUtil(arr, 0, n - 1, ratio); } }; int main() { Progression pg; int arr[] = {1, 3, 27, 81}; int n = sizeof(arr) / sizeof(arr[0]); cout << "The missing element is: " << pg.missingElement(arr, n); }
Kết quả
The missing element is: 9