Chương trình C ++ để tìm số lượng bàn phím tối thiểu có thể bị đánh cắp

Giả sử chúng ta có một mảng A với n phần tử. Có một cửa hàng điện tử, nơi một vụ cướp đã thực hiện vào đêm qua. Tất cả các bàn phím có mặt bên trong cửa hàng đều được đánh số theo thứ tự tăng dần từ một số nguyên x. Ví dụ:đối với x =4 và có 3 bàn phím trong cửa hàng, thì các thiết bị có chỉ số 4, 5 và 6. Nếu x =10 và có 7 trong số chúng thì bàn phím có chỉ số 10, 11, 12, 13, 14, 15 và 16. Sau khi cướp, chỉ còn n bàn phím. Chúng có các chỉ mục được lưu trữ trong mảng A. Chúng tôi phải tìm ra số bàn phím tối thiểu có thể đã bị đánh cắp.

Vì vậy, nếu đầu vào là A =[10, 13, 12, 8], thì đầu ra sẽ là 2, vì nếu x =8 thì số bàn phím bị đánh cắp tối thiểu là 2. Bàn phím có chỉ số 9 và 11 đã bị đánh cắp.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

sort the array A
n := size of A
return A[n - 1] - A[0] + 1 - n

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
      sort(A.begin(), A.end());
int n = A.size();
   return A[n - 1] - A[0] + 1 - n;
}
int main() {
   vector<int> A = { 10, 13, 12, 8 };
   cout << solve(A) << endl;
}

Đầu vào

{ 10, 13, 12, 8 }

Đầu ra

2