Chương trình C++ tìm số bàn phím bị mất tối thiểu

Cửa hàng bán bàn phím đánh số liên tiếp từ x. Sau cướp, còn n bàn phím chỉ số trong mảng A. Tìm số bàn phím bị mất tối thiểu.

Ví dụ

Với A=[10,13,12,8], đầu ra 2. Nếu x=8, dãy 8..13 có 6 bàn phím, còn 4 → mất 2 (số 9 và 11).

Giải thuật

Sắp xếp A. Số bàn phím ban đầu tối thiểu = A[n-1] - A[0] + 1 (từ min đến max). Số bị mất = A[n-1] - A[0] + 1 - n.

Mã C++

#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 / Đầu ra

Input: { 10, 13, 12, 8 }
Output: 2