मान लीजिए हमारे पास पूर्णांकों की एक सरणी nums और एक धनात्मक पूर्णांक k है, हमें ढूंढना है कि क्या इस सरणी को k लगातार संख्याओं के सेट में विभाजित करना संभव है। इसलिए हमें True लौटाना है यदि यह संभव है अन्यथा False लौटाएं। इसलिए यदि इनपुट [1,2,3,3,4,4,5,6] और k = 4 है, तो आउटपुट true होगा। ऐसा इसलिए है क्योंकि, हम सरणी को इस तरह विभाजित कर सकते हैं कि [1,2,3,4] और [3,4,5,6]
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- एक मैप
mबनाएं,n := nums सरणी का आकारसेट करें nums में प्रत्येक तत्व eके लिए:m[e]को 1 से बढ़ाएं
cnt := 0nums सरणी को क्रमबद्ध करेंi = 0 से nतक:x := nums[i]- यदि
m[x-1] == 0 और m[x] > 0:l := kwhile k > 0:- यदि
m[x] > 0, तोm[k]के मान को 1 से घटाएं, अन्यथा false लौटाएं x और cntको 1 से बढ़ाएं, औरkको 1 से घटाएं
- यदि
k := l
- जब
cnt == nतो true लौटाएं, अन्यथा false
उदाहरण
#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;
}
};
int 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