C++ में स्मॉलेस्ट रेंज II (Smallest Range II)

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, प्रत्येक पूर्णांक A[i] के लिए हमें या तो x = -K या x = K चुनना है, और x को A[i] में जोड़ना है (केवल एक बार)। इस प्रक्रिया के बाद, हमारे पास कुछ ऐरे B होगा। हमें B के अधिकतम मान और न्यूनतम मान के बीच सबसे छोटे संभव अंतर को खोजना है।

उदाहरण के लिए, यदि इनपुट A = [0,10], K = 2 है, तो आउटपुट 6 होगा, क्योंकि B = [2,8]।

समाधान दृष्टिकोण

1. ret := 0, n := A का आकार

2. A को सॉर्ट करें

3. ret := A[n-1] - A[0]

4. right := A[n-1] - K, left := A[0] + K

5. i को 0 से n-2 तक: mx = max(A[i]+K, right), mn = min(A[i+1]-K, left), ret = min(ret, mx-mn)

6. ret लौटाएं

C++ कार्यान्वयन

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

class Solution { 
public: 
    int smallestRangeII(vector<int>& A, int k) { 
        int ret = 0; 
        int n = A.size(); 
        sort(A.begin(), A.end()); 
        ret = A[n - 1] - A[0]; 
        int mx, mn; 
        int right = A[n - 1] - k; 
        int left = A[0] + k; 
        for(int i = 0; i < n - 1; i++){ 
            mx = max(A[i] + k, right); 
            mn = min(A[i + 1] - k, left); 
            ret = min(ret, mx - mn); 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<int> v = {0, 10}; 
    Solution ob; 
    cout << (ob.smallestRangeII(v, 2)); 
    return 0; 
}

इनपुट

[0,10] 2

आउटपुट

6