সি++-এ অ্যারেতে রেঞ্জের সব উপাদান থাকতে যোগ করা প্রয়োজনীয় উপাদান বের করা

এই সমস্যায় আমাদের একটি অ্যারে arr[] দেওয়া হয়েছে যাতে n সংখ্যক সংখ্যা রয়েছে। আমাদের কাজ হলো অ্যারেতে রেঞ্জের সব উপাদান থাকতে যোগ করা প্রয়োজনীয় উপাদান বের করা।

সমস্যা বিবরণ: এখানে আমাদের সেই উপাদানগুলো বের করতে হবে যেগুলো অ্যারেতে যোগ করলে রেঞ্জের সব উপাদান অ্যারেতে থাকবে। রেঞ্জটি হলো অ্যারের সবচেয়ে ছোট উপাদান থেকে অ্যারের সবচেয়ে বড় উপাদান পর্যন্ত।

উদাহরণ দিয়ে বুঝি

ইনপুট: arr[] = {5, 8, 3, 1, 6, 2}

আউটপুট: ২

ব্যাখ্যা:

রেঞ্জটি হলো ১ থেকে ৮,

যোগ করা প্রয়োজনীয় উপাদানগুলো হলো ৪ এবং ৭।

সমাধানের পদ্ধতি

একটি সহজ সমাধান হলো রেঞ্জের কোন উপাদান অ্যারেতে নেই তা বের করা। এর জন্য অ্যারেটি সর্ট করে পরের উপাদানটি উপস্থিত কিনা চেক করতে হবে।

অ্যালগরিদম:

ধাপ ১: অ্যারেটি সর্ট করুন।
ধাপ ২: অ্যারেটি লুপ চালান, i -> 0 থেকে n-1।
ধাপ ২.১: যদি arr[i] + 1 != arr[i+1] হয়, কাউন্ট বাড়ান।
ধাপ ৩: কাউন্ট প্রিন্ট করুন।

সমাধান minhaj করার প্রোগ্রাম

#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; 
}

আউটপুট

The number of elements required to complete the range is 1