Why this code getting TLE? problem - Remove Bad Elements

help
,
1

#include

using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL) ;
int t;
cin>>t;
while(t–)
{
int n,ct,b[100000];
cin>>n;
int a[100000];
bool flag = false;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++){
ct=1;
for(int j=i+1;j<n;j++){
if(a[i]==a[j])
{
ct++;
}
}
b[i]=ct;
}

    int max = b[0];
    for(int i=1;i<n;i++){
        if(b[i]>max){
            max=b[i];
        }
    }
    if(max>0){
      cout<<n-max<<endl;
    }else if(max==0){
      cout<<n-1<<endl;
    }
}
return 0;

}

2

The inputs of this solution can be large, it will often result in TLE if your solution is not fast enough or your solution has too many loops.

Here’s my Solution:

#include <iostream>
#include <set>
#include <bits/stdc++.h>

using namespace std;

int main() {
	// your code goes here
	int t;
	cin >> t;
	while (t--) {
	    int N;
	    cin >> N;
	    int arr[N];
	    set<int> s1;
	    for (int i = 0; i < N; ++i) {
	        cin >> arr[i];
	        s1.insert(arr[i]);
	    }
	    sort(arr, arr + N);
	    int count = 0;
	    int res = 0;
	    if (s1.size() == 1) {
	        cout << 0 << "\n"; 
	    }
	    else {
	       int max_count = 0;
	       int count = 0;
	       int start = 0;
	       int last = 0;
	       int el;
	       int i = 0;
	       while (i <= N) {
	           el = arr[last];
	           if (arr[i] != el) {
	               start = last;
	               last = i;
	               int el_count = last - start;
	               if (el_count > max_count) {
	                   count += max_count;
	                   max_count = el_count;
	               }
	               else {
	                   count += el_count;
	               }
	           }
	           i += 1;
	       }
	       cout << count << "\n";
	    }
	}
	return 0;
}

You can use a set and see if size of set is 1. If so then print 0 as the answer. Else you can sort the array and simply count the occurrence of numbers.

Here’s my first solution which is correct but not fast enough, it was also running into TLE at the 4th Task:

#include <iostream>
#include <set>
#include <bits/stdc++.h>

using namespace std;

int main() {
	// your code goes here
	int t;
	cin >> t;
	while (t--) {
	    int N;
	    cin >> N;
	    int arr[N];
	    set<int> s1;
	    for (int i = 0; i < N; ++i) {
	        cin >> arr[i];
	        s1.insert(arr[i]);
	    }
	    sort(arr, arr + N);
	    int count = 0;
	    int res = 0;
	    if (s1.size() == 1) {
	        cout << 0 << "\n"; 
	    }
	    else {
	        int jdx = 0;
	        for (auto itr = s1.begin(); itr != s1.end(); ++itr) {
	            int el = *itr;
	            int max_count = 0;
	            int j = jdx;
	            while (j < N) {
	                if (arr[j] == el) {
	                    max_count += 1;
	                    
	                }
	                else {
	                    if (max_count > 0) {
	                        break;
	                    }
	                }
	                j += 1;
	            }
	            if (max_count > count) {
	                res += count;
	                count = max_count;
	            }
	            else {
	                res += max_count;
	            }
	        }
	        cout << res << "\n";
	    }
	}
	return 0;
}