Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सरणी को K लगातार संख्याओं के सेट में विभाजित करना


मान लीजिए हमारे पास पूर्णांकों की एक सरणी 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 := 0
  • nums सरणी को क्रमबद्ध करें
  • i = 0 से n तक:
    • x := nums[i]
    • यदि m[x-1] == 0 और m[x] > 0:
      • l := k
      • while 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

  1. - C++ में ऐरे में अधिकतम सतत अभाज्य संख्याओं की संख्या

    हमें अभाज्य संख्याओं का एक ऐरे दिया गया है, जो यादृच्छिक क्रम में व्यवस्थित है। ऐरे का आकार N है। लक्ष्य ऐरे में सतत अभाज्य संख्याओं का सबसे लंबा अनुक्रम ढूंढना है।अभाज्य संख्या वह है जिसके केवल दो गुणनखंड होते हैं, 1 और संख्या स्वयं। 1,2,3,5,7,11,13... अभाज्य संख्याएं हैं जबकि 4,6,8,9,10...20 गैर-अ

  1. - C++ में बाइनरी सर्कुलर ऐरे में अधिकतम सतत 1 या 0

    हमें एक सर्कुलर ऐरे दिया गया है। सर्कुलर ऐरे वह ऐरे है जिसके लिए हम मानते हैं कि पहला तत्व अंतिम तत्व के बगल में आता है। इसका उपयोग क्यू को लागू करने के लिए किया जाता है। इसलिए हमें उस ऐरे में अधिकतम सतत 1 या 0 की संख्या गिननी है।आइए उदाहरणों से समझते हैं।इनपुट - Arr[] = { 1,1,0,1,0,1,0,1,1,1 }आउटपु

  1. C++ में ऐरे में सभी अभाज्य संख्याओं का गुणनफल C++ में ऐरे में सभी अभाज्य संख्याओं का गुणनफल

    कुछ एलिमेंट्स के साथ एक इंटीजर ऐरे arr[] दिया गया है, कार्य उस ऐरे की सभी अभाज्य संख्याओं का गुणनफल निकालना है। अभाज्य संख्याएं वे संख्याएं होती हैं जो या तो 1 से विभाज्य होती हैं या स्वयं संख्या से, या एक अभाज्य संख्या वह संख्या है जो 1 और स्वयं संख्या को छोड़कर किसी अन्य संख्या से विभाज्य नहीं ह