Số bị thiếu trong cấp số học bằng C ++

Giả sử chúng ta có một mảng biểu diễn các phần tử của cấp số cộng theo thứ tự. Thiếu một phần tử. Chúng ta phải tìm ra yếu tố còn thiếu. Vì vậy, nếu arr =[2, 4, 8, 10, 12, 14], đầu ra là 6, vì 6 bị thiếu.

Sử dụng tìm kiếm nhị phân, chúng ta có thể giải quyết vấn đề này. Chúng ta sẽ đi đến phần tử giữa, sau đó kiểm tra xem sự khác biệt giữa phần giữa và bên cạnh phần giữa có giống với diff hay không. Nếu không, thì phần tử bị thiếu sẽ xuất hiện giữa các chỉ số giữa và giữa + 1. Nếu phần tử ở giữa là phần tử thứ n / 2 trong AP, thì phần tử bị thiếu nằm ở nửa bên phải, ngược lại ở nửa bên trái.

Ví dụ (C ++)

#include <iostream>
using namespace std;
#define INT_MAX 999999
class Progression {
   public:
   int missingUtil(int arr[], int left, int right, int diff) {
      if (right <= left)
         return INT_MAX;
      int mid = left + (right - left) / 2;
      if (arr[mid + 1] - arr[mid] != diff)
         return (arr[mid] + diff);
      if (mid > 0 && arr[mid] - arr[mid - 1] != diff)
         return (arr[mid - 1] + diff);
      if (arr[mid] == arr[0] + mid * diff)
         return missingUtil(arr, mid + 1, right, diff);
      return missingUtil(arr, left, mid - 1, diff);
   }
   int missingElement(int arr[], int n) {
      int diff = (arr[n - 1] - arr[0]) / n;
      return missingUtil(arr, 0, n - 1, diff);
   }
};
int main() {
   Progression pg;
   int arr[] = {2, 4, 8, 10, 12, 14};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "The missing element is: " << pg.missingElement(arr, n)<<endl;
}

Đầu vào

[2,4,8,10,12,14]

Đầu ra

The missing element is: 6