หาจำนวนสมาชิกที่ต้องเพิ่มให้ครบช่วงในอาร์เรย์ C++

ปัญหา

ได้รับอาร์เรย์ arr[] หาจำนวนสมาชิกที่ต้องเพิ่มเข้าไป เพื่อให้ครบทุกจำนวนในช่วง [min, max] ของอาร์เรย์

ตัวอย่าง

อินพุต: arr[] = {5, 8, 3, 1, 6, 2}

เอาต์พุต: 2

คำอธิบาย: ช่วงคือ 1 ถึง 8 ขาด 4 และ 7

แนวทางแก้ปัญหา

1. เรียงลำดับอาร์เรย์
2. วนลูปตรวจสอบว่า arr[i]+1 == arr[i+1] หรือไม่ ถ้าไม่เท่ากัน นับจำนวนที่ขาด

โปรแกรมตัวอย่าง

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

int calcEleRequired(int arr[], int n) {
    sort(arr, arr + n);
    int count = 0;
    for (int i = 0; i < n - 1; i++)
        if (arr[i] + 1 != arr[i + 1])
            count++;
    return count;
}

int main() {
    int arr[] = {5, 7, 3, 1, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Elements needed to complete range: " << calcEleRequired(arr, n);
    return 0;
}

ผลลัพธ์

Elements needed to complete range: 1