मान लीजिए कि हमारे पास पूर्णांक संख्याओं की एक सरणी है और एक सकारात्मक पूर्णांक k है, तो हमें यह पता लगाना होगा कि क्या इस सरणी को k लगातार संख्याओं के सेट में विभाजित करना संभव है। इसलिए यदि संभव हो तो हमें ट्रू वापस करना होगा अन्यथा गलत लौटाएं। तो अगर इनपुट [1,2,3,3,4,4,5,6] और k =4 जैसा है, तो आउटपुट सही होगा। ऐसा इसलिए है, क्योंकि हम सरणी को इस तरह विभाजित कर सकते हैं कि [1,2,3,4] और [3,4,5,6]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक नक्शा m बनाएं, n सेट करें:=अंकों की सरणी का आकार
- प्रत्येक तत्व के लिए ई अंकों में
- m[e] को 1 से बढ़ाएं
- सीएनटी:=0
- संख्या सरणी को क्रमबद्ध करें
- मैं के लिए 0 से n की सीमा में
- x :=nums[i]
- यदि m[x – 1] =0 और m[x]> 0
- l :=k
- जबकि कश्मीर> 0
- अगर m[x]> 0, तो m[k] के मान को 1 से घटाएं, नहीं तो झूठी वापसी करें
- x और cnt को 1 से बढ़ाएं और k को 1 से घटाएं
- k :=l
- सीएनटी =एन होने पर सही लौटें, अन्यथा गलत
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x - 1] == 0 && m[x] > 0){
int l = k;
while(k>0){
if(m[x] > 0){
m[x]--;
} else return false;
x++;
k--;
cnt++;
}
k = l;
}
}
return cnt == n;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,6};
Solution ob;
cout << (ob.isPossibleDivide(v, 4));
} इनपुट
[1,2,3,3,4,4,5,6] 4
आउटपुट
1