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

C++ में ऐरे को यूनिक बनाने के लिए न्यूनतम इंक्रीमेंट (Minimum Increment to Make Array Unique)


मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, यहां एक चाल में किसी भी A[i] को चुनकर उसे 1 से बढ़ाना शामिल है। हमें हर मान को A में यूनिक बनाने के लिए चालों की न्यूनतम संख्या खोजनी है।

उदाहरण के लिए, यदि इनपुट [3,2,1,2,1,7] है, तो आउटपुट 6 होगा, क्योंकि 6 चालों के बाद ऐरे [3,4,1,2,5,7] हो सकता है, यह दिखाया जा सकता है कि 5 या कम चालों में ऐरे के सभी मान विशिष्ट होना असंभव है।

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

  1. ret := 0

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

  3. i को 1 से n-1 तक: यदि A[i] ≤ A[i-1], तो ret += (A[i-1] + 1) - A[i], और A[i] = A[i-1] + 1

  4. ret लौटाएं

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

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

class Solution { 
public: 
    int minIncrementForUnique(vector<int>& A) { 
        int ret = 0; 
        sort(A.begin(), A.end()); 
        for(int i = 1; i < A.size(); i++){ 
            if(A[i] <= A[i - 1]){ 
                ret += (A[i - 1] + 1) - A[i]; 
                A[i] = A[i - 1] + 1; 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<int> v1 = {3,2,1,2,1,7}; 
    Solution ob; 
    cout << (ob.minIncrementForUnique(v1)); 
    return 0; 
}

इनपुट

[3,2,1,2,1,7]

आउटपुट

6
  1. - C++ में सरणी पर ऑपरेशन करके सभी तत्वों को 0 बनाने के लिए न्यूनतम ऑपरेशन

    समस्या कथन आकार N की एक सरणी दी गई है और प्रत्येक तत्व या तो 1 या 0 है। सभी तत्वों को शून्य में बदलने के लिए किए जाने वाले न्यूनतम ऑपरेशन की गणना करें। कोई निम्न ऑपरेशन कर सकता है: यदि कोई तत्व 1 है, तो आप उसका मान 0 के बराबर बदल सकते हैं, तब: यदि अगला लगातार तत्व 1 है, तो यह स्वचालित रूप से 0

  1. - C++ में सरणी के GCD को k का गुणक बनाने के लिए न्यूनतम ऑपरेशन

    मान लीजिए हमारे पास एक सरणी arr और एक अन्य मान k है। हमें सरणी के GCD को k का गुणक बनाने के लिए न्यूनतम ऑपरेशंस की संख्या ढूंढनी है। यहां ऑपरेशन मान को बढ़ाना या घटाना है। मान लीजिए सरणी {4, 5, 6} है, और k 5 है। हम 4 को 1 से बढ़ा सकते हैं, और 6 को 1 से घटा सकते हैं, तो यह 5 बन जाता है। यहां ऑपरेशंस

  1. - C++ में को-प्राइम ऐरे बनाने के लिए न्यूनतम इंसर्शन

    इस सेक्शन में हम एक और दिलचस्प समस्या देखेंगे। मान लीजिए हमारे पास N एलिमेंट्स का एक ऐरे है। हमें इस ऐरे को को-प्राइम ऐरे बनाने के लिए न्यूनतम इंटरसेक्शन पॉइंट्स ढूंढने हैं। को-प्राइम ऐरे में हर दो लगातार एलिमेंट्स का gcd 1 होता है। हमें ऐरे भी प्रिंट करना है।मान लीजिए हमारे पास {5, 10, 20} जैसे एलि