C++ में k से कम या बराबर सभी एलिमेंट्स को एक साथ लाने के लिए न्यूनतम स्वैप

समस्या कथन

n पॉजिटिव पूर्णांकों का एक ऐरे और एक संख्या k दी गई है। उन सभी संख्याओं को एक साथ लाने के लिए आवश्यक न्यूनतम स्वैप की संख्या ढूंढें जो k से कम या बराबर हैं।

उदाहरण

यदि इनपुट ऐरे है = {1, 5, 4, 7, 2, 10} और k = 6 तो 1 स्वैप आवश्यक है यानी एलिमेंट 7 को 2 से स्वैप करें।

एल्गोरिदम

• उन सभी एलिमेंट्स को गिनें जो 'k' से कम या बराबर हैं। मान लें कि गिनती 'cnt' है
• लंबाई 'cnt' की विंडो के लिए टू पॉइंटर तकनीक का उपयोग करके, हर बार ट्रैक करें कि इस रेंज में कितने एलिमेंट्स 'k' से बड़े हैं। मान लें कि कुल गिनती 'outOfRange' है।
• चरण 2 को लंबाई 'cnt' की हर विंडो के लिए दोहराएं और उनमें 'outOfRange' की गिनती का न्यूनतम लें। यह अंतिम उत्तर होगा।

उदाहरण

#include 
using namespace std;

int getMinSwaps(int *arr, int n, int k) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] <= k) {
            ++cnt;
        }
    }
    int outOfRange = 0;
    for (int i = 0; i < cnt; ++i) {
        if (arr[i] > k) {
            ++outOfRange;
        }
    }
    int result = outOfRange;
    for (int i = 0, j = cnt; j < n; ++i, ++j) {
        if (arr[i] > k) {
            --outOfRange;
        }
        if (arr[j] > k) {
            ++outOfRange;
        }
        result = min(result, outOfRange);
    }
    return result;
}

int main() {
    int arr[] = {1, 5, 4, 7, 2, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << "Minimum swaps = " << getMinSwaps(arr, n, k) << endl;
    return 0;
}

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

आउटपुट

Minimum swaps = 1