সমস্যা বিবরণ
N সংখ্যক ইন্টিজারের একটি অ্যারে দেওয়া আছে, অ্যারে উপাদানগুলোর পুনর্বিন্যাস করুন যাতে পরবর্তী অ্যারে উপাদানটি পূর্ববর্তী উপাদানটির চেয়ে বড় হয় অর্থাৎ arr[i+1] > arr[i]।
উদাহরণ
যদি ইনপুট অ্যারে হয় {300, 400, 400, 300} তবে পুনর্বিন্যাস করা অ্যারে হবে:
{300, 400, 300, 400}। এই সমাধানে arr[i+1] > arr[i] শর্ত পূরণকারী ২টি ইন্ডেক্স পাওয়া যায়। তাই উত্তর ২।
অ্যালগরিদম
- যদি সব উপাদান আলাদা হয়, তবে উত্তর সিম্পলি 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
