Số phần tử cần thêm để mảng chứa toàn bộ dải giá trị trong C++

Cho mảng arr[] n phần tử. Tìm số lượng phần tử tối thiểu cần thêm vào mảng để mảng chứa **toàn bộ các số nguyên liên tiếp** từ min(arr) đến max(arr).

Ví dụ

Đầu vào: arr[] = {5, 8, 3, 1, 6, 2}

Đầu ra: 2

Giải thích: Min=1, Max=8. Dải [1..8] cần {1,2,3,4,5,6,7,8}. Mảng thiếu {4, 7} => Cần thêm 2 phần tử.

Phương pháp giải

1. Tìm Min, Max của mảng.
2. Số phần tử cần có trong dải = Max - Min + 1.
3. Số phần tử riêng biệt hiện có trong mảng (dùng set hoặc sort + unique).
4. Kết quả = (Max - Min + 1) - Số phần tử riêng biệt.

Chương trình minh họa (Tối ưu O(N log N) hoặc O(N))

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

int countElementsToAdd(int arr[], int n) {
    if (n == 0) return 0;
    
    int minVal = arr[0], maxVal = arr[0];
    unordered_set<int> uniqueVals;
    
    for (int i = 0; i < n; i++) {
        minVal = min(minVal, arr[i]);
        maxVal = max(maxVal, arr[i]);
        uniqueVals.insert(arr[i]);
    }
    
    int totalNeeded = maxVal - minVal + 1;
    int currentUnique = uniqueVals.size();
    
    return totalNeeded - currentUnique;
}

int main() {
    int arr[] = {5, 7, 3, 1, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "So phan tu can them: " << countElementsToAdd(arr, n);
    return 0;
}

Đầu ra

So phan tu can them: 1

(Mảng: 1,2,3,5,6,7. Min=1, Max=7. Cần 7 phần tử. Có 6 phần tử riêng biệt. Thiếu 1 phần tử: số 4).