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

C++ में अधिकतम 1 स्वैप का उपयोग करके निश्चित बिंदुओं की अधिकतम संख्या


समस्या कथन

0 से N-1 तक के N तत्वों का एक क्रमपरिवर्तन दिया गया है। एक निश्चित बिंदु वह इंडेक्स है जिस पर मान इंडेक्स के समान होता है यानी arr[i] = i। आपको अधिकतम 1 स्वैप करने की अनुमति है। अधिकतम निश्चित बिंदुओं की संख्या ढूंढें जो आप प्राप्त कर सकते हैं।

उदाहरण

यदि इनपुट ऐरे है {0, 1, 2, 3, 4, 6, 5} तो उत्तर 7 है।

  • निश्चित बिंदु को समायोजित करने के लिए, हमें 6 और 5 को स्वैप करना होगा
  • इसके बाद पूरा ऐरे निश्चित बिंदु बन जाता है और निश्चित बिंदु का अधिकतम मान 7 होता है।

एल्गोरिदम

  • एक ऐरे pos बनाएं जो इनपुट ऐरे में प्रत्येक तत्व की स्थिति को ट्रैक करे
  • अब, हम ऐरे को ट्रैवर्स करते हैं और निम्न मामले होते हैं -
    • यदि, a[i] = i। हम बस काउंट बढ़ा सकते हैं और आगे बढ़ सकते हैं
    • यदि, pos[i] = a[i] जिसका अर्थ है कि 2 पदों को स्वैप करने से i और a[i] निश्चित बिंदु बन जाएंगे, इसलिए काउंट 2 से बढ़ जाएगा। ध्यान रखें कि स्वैप अधिकतम एक बार किया जा सकता है।
  • ट्रैवर्सल के अंत में, यदि हमने कोई स्वैप नहीं किया है, तो इसका मतलब है कि हमारा स्वैप काउंट को 2 से बढ़ाने में सक्षम नहीं था, इसलिए अब यदि कम से कम 2 तत्व हैं जो निश्चित बिंदु नहीं हैं, तो हम उनमें से एक को निश्चित बिंदु बनाने के लिए स्वैप कर सकते हैं, यानी काउंट को 1 से बढ़ा सकते हैं।

उदाहरण

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

int getMaximumFixedPoints(int arr[], int n) {
    int i, pos[n], count = 0, swapped = 0;
    for (i = 0; i < n; i++)
        pos[arr[i]] = i;
    
    for (i = 0; i < n; i++) {
        if (arr[i] == i) {
            count++;
        } else if (swapped == 0 && pos[i] == arr[i]) {
            count += 2;
            swapped = 1;
        }
    }
    
    if (swapped == 0 && count < n - 1) {
        count++;
    }
    
    return count;
}

int main() {
    int arr[] = {0, 1, 2, 3, 4, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
    return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -

Maximum edges = 7

  1. C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें

    यूक्लिडियन प्लेन ज्यामिति में एक चतुर्भुज चार शीर्षों और चार किनारों के साथ एक बहुभुज बनाता है। नाम 4-gon आदि। चतुर्भुजों के अन्य नामों में शामिल हैं और कभी-कभी उन्हें वर्ग, डिस्प्ले स्टाइल आदि के रूप में भी जाना जाता है।इस लेख में, हम दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करने के दृष

  1. C++ में N सेगमेंट का उपयोग करके सेवन सेगमेंट डिस्प्ले पर प्रदर्शित अधिकतम संख्या C++ में N सेगमेंट का उपयोग करके सेवन सेगमेंट डिस्प्ले पर प्रदर्शित अधिकतम संख्या

    दिया गया कार्य N सेगमेंट का उपयोग करके किसी भी संख्या के सेवन सेगमेंट डिस्प्ले पर प्रदर्शित की जा सकने वाली अधिकतम संख्या ढूंढना है।उदाहरण से समझते हैंइनपुट - N=5आउटपुट - 71व्याख्या - सबसे बड़ी संख्या सेवन सेगमेंट डिस्प्ले पर इस प्रकार प्रदर्शित होगी।इनपुट - N=6आउटपुट - 111प्रयुक्त दृष्टिकोणनिम्नलिख

  1. - C++ में XOR को अधिकतम बनाने के लिए हटाए जाने वाले न्यूनतम तत्व

    समस्या कथन एक संख्या N दी गई है। 1 से N के बीच के न्यूनतम तत्वों की संख्या ढूंढें जिन्हें हटाया जाए ताकि शेष तत्वों से प्राप्त XOR अधिकतम हो। एल्गोरिदम 1. यदि n 1 या 2 है तो किसी तत्व को हटाने की आवश्यकता नहीं है। उत्तर शून्य है। 2. एक संख्या ढूंढें जो 2 की घात है और n से बड़ी या बराबर है। इसे next