Các phần tử sẽ được thêm vào để tất cả các phần tử của một dải ô đều có trong mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số. Nhiệm vụ của chúng ta là tạo một chương trình để tìm số phần tử được thêm vào để tất cả các phần tử của một dải ô đều có mặt trong mảng.

Mô tả sự cố: Ở đây, chúng ta cần tìm số phần tử cần thêm vào mảng để đảm bảo rằng tất cả các phần tử của một phạm vi đều có mặt trong mảng. Phạm vi từ smallElement of array to lớn nhất của mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra: 2

Giải thích:

Phạm vi từ 1 đến 8,

Các phần tử sẽ được thêm vào là 4 và 7.

Phương pháp tiếp cận Giải pháp -

Một giải pháp đơn giản cho vấn đề là tìm phần tử nào của dãy không có trong mảng. Đối với điều này, chúng ta cần sắp xếp mảng và sau đó tìm xem phần tử tiếp theo có hiện diện hay không.

Thuật toán -

Bước 1: sắp xếp mảng.

Bước 2: lặp qua mảng, for i -> 0 to n-1.

Bước 2.1: nếu arr [i] + 1! =arr [i + 1], hãy tăng số lượng.

Bước 3: số lượng in.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

int calcEleRequired(int arr[], int n)
{
   int count = 0;
   sort(arr, arr + n);
   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<<"The number of elements required to complete the range is "<<calcEleRequired(arr, n);
   return 0;
}

Đầu ra -

The number of elements required to complete the range is 1