सबसे बड़ा अंतराल खोजें जिसमें दिए गए N पूर्णांकों में से ठीक एक हो C++ में

मान लीजिए हमारे पास N अलग-अलग पूर्णांकों का एक ऐरे है। हमें अंतराल [L, R] में अधिकतम तत्व खोजना है जैसे कि अंतराल में दिए गए N पूर्णांकों में से ठीक एक हो और 1 <= L <= R <= 10^5।

तो यदि ऐरे Arr = [5, 10, 200] जैसा है, तो आउटपुट 99990 होगा। तो सभी संभावित अंतराल [1, 9], [6, 199] और [11, 100000] हैं। अंतिम में अधिकतम पूर्णांक जैसे 99990 हैं।

विचार सरल है। हम उस तत्व को फिक्स करेंगे जिसे हम अपने अंतराल में रखना चाहते हैं। अब, हम देखेंगे कि हम अपने अंतराल को बाएं और दाएं कैसे बढ़ा सकते हैं बिना अन्य तत्वों को ओवरलैप किए। तो हमें पहले ऐरे को सॉर्ट करना होगा, फिर एक फिक्स तत्व के लिए, हम पिछले और अगले तत्व का उपयोग करके अंत निर्धारित करेंगे। हम कॉर्नर केस का ध्यान रखेंगे। तो जब हम पहले और अंतिम अंतराल को फिक्स कर रहे हों। इस तरह हर तत्व i के लिए, हम अंतराल की अधिकतम लंबाई खोजते हैं।

उदाहरण

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int maximumSize(vector<int>& vec, int n) {
    vec.push_back(0);
    vec.push_back(100001);
    n += 2;
    sort(vec.begin(), vec.end());
    int max_value = 0;
    for (int i = 1; i < n - 1; i++) {
        int Left = vec[i - 1] + 1;
        int Right = vec[i + 1] - 1;
        int count = Right - Left + 1;
        max_value = max(max_value, count);
    }
    return max_value;
}

int main() {
    vector<int> v;
    v.push_back(200);
    v.push_back(10);
    v.push_back(5);
    int n = v.size();
    cout << "Maximum Size is: " << maximumSize(v, n);
}

आउटपुट

Maximum Size is: 99990