I don’t know if my logic is correct or not. Can anyone please help me out, my solution was accepted but after reading this editorial. I found my solution nowhere close to the discussion.
So this is what I did.
I found the frequency of element which has occured the most, say sequence is (1,4,6,1,3,6). So max frequency is 2 be it for 6 or 1 doesn’t matter.
Since we have to find the minimum number of moves so I substract the max frequency from size of sequnce. In above case the size is 6. so minimum number of swappings is 6-2=4
Let’s take One of the given testcase 9 8 1 8
so max frequency is 2 (we are not bothered to find which element has max frequemcy, we just need max frequency) so length is 4
Therefore 4-2=2
Can someone share there thoughts about this approach. It was accepted but still I’m confused if it’s right!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int x[n];
for(int i = 0; i < n; i++) {
cin >> x[i];
}
int ans[101] = {0};
for(int i = 0; i < n; i++) {
ans[x[i]]++;
}
int largest = -1;
for(int i = 0; i < 100; i++) {
largest = max(ans[i], largest);
}
cout << n - largest << endl;
}
}
int main() {
// your code goes here
int t;
cin >> t;
while (t–){
int n;
cin >> n;
char a[n];
for(int i=0; i<n; i++){
cin >> a[i];
}
int count=0, countmain=0,ele,step=0; // for finding max number of same same element.
for(int i=0; i<n; i++){ //count main is maxixmum no of same element
count=0;
for(int j=0; j<n; j++){
if(a[i]==a[j]) count++;
}
if (count > countmain){
countmain=count;
ele = a[i];
}
}
for(int j=0; j<=n; j++){
for(int i=0; i<n; i++){
if(a[i]==ele) continue;
else if (a[i-1]==ele){
a[i]=a[i-1];
step++;
}
else if (a[i+1]==ele) {
a[i]=a[i+1];
step++;
}
else continue;
}