C++ में a[i+1] > a[i] वाले तत्वों को अधिकतम करना

समस्या कथन

N पूर्णांकों का एक ऐरे दिया गया है, ऐरे तत्वों को पुनर्व्यवस्थित करें जैसे कि अगला ऐरे तत्व पिछले तत्व से बड़ा हो arr[i+1] > arr[i]।

उदाहरण

यदि इनपुट ऐरे है {300, 400, 400, 300} तो पुनर्व्यवस्थित ऐरे होगा:

{300, 400, 300, 400}। इस समाधान में हमें शर्त arr[i+1] > arr[i] के साथ 2 इंडेक्स मिलते हैं। इसलिए उत्तर 2 है।

एल्गोरिदम

• यदि सभी तत्व विशिष्ट हैं, तो उत्तर केवल n-1 है जहां n ऐरे में तत्वों की संख्या है।
• यदि तत्व दोहराए जा रहे हैं, तो उत्तर n - maxFrequency है।

उदाहरण

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

int getMaxIndices(int* arr, int n) {
    int count[MAX] = {0};
    for (int i = 0; i < n; ++i) {
        count[arr[i]]++;
    }
    int maxFrequency = 0;
    for (int i = 0; i < n; ++i) {
        if (count[arr[i]] > maxFrequency) {
            maxFrequency = count[arr[i]];
        }
    }
    return n - maxFrequency;
}

int main() {
    int arr[] = {300, 400, 300, 400};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Answer = " << getMaxIndices(arr, n) << endl;
    return 0;
}

आउटपुट

Answer = 2