मान लीजिए कि हमारे पास अलग-अलग पूर्णांकों की एक सूची है, जिन्हें अंक कहते हैं। हमें सबसे बड़े अंतराल (समावेशी) [प्रारंभ, अंत] का आकार इस तरह निकालना होगा कि इसमें अंकों में अधिकतम एक संख्या हो।
इसलिए, यदि इनपुट nums =[10, 6, 20] की तरह है, तो आउटपुट 99990 होगा, क्योंकि सबसे बड़ा अंतराल [11, 100000] है, इसमें केवल 20 हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=-इन्फ
-
अंत:=100000
-
पिछला :=1
-
सरणी संख्याओं को क्रमबद्ध करें
-
n :=अंकों का आकार
-
इनिशियलाइज़ i :=0 के लिए, जब i <अंकों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -
-
अगर मैं + 1 <एन, तो -
-
उच्च:=अंक [i + 1] - 1
-
-
अन्यथा
-
उच्च :=अंत
-
-
अगर मैं - 1>=0, तो -
-
कम :=पिछला + 1
-
-
अन्यथा
-
कम :=पिछला
-
-
पिछला:=अंक[i]
-
ret :=अधिकतम उच्च - निम्न + 1 और ret
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int> &nums) {
int ret = INT_MIN;
int end = 100000;
int prev = 1;
sort(nums.begin(), nums.end());
int n = nums.size();
int low, high;
for (int i = 0; i < nums.size(); i++) {
if (i + 1 < n) {
high = nums[i + 1] - 1;
} else
high = end;
if (i - 1 >= 0) {
low = prev + 1;
} else
low = prev;
prev = nums[i];
ret = max(high - low + 1, ret);
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {10, 6, 20};
cout << (ob.solve(v));
} इनपुट
{10, 6, 20} आउटपुट
99990