My code for RRCOPY is not working

general
1

Can anyone point out the error?

#include<iostream>
#include<vector>
using namespace std;
vector<long int> a;

int search(long int b) 
{
for(long int i = 0;i < a.size();i++)
        if(a.at(i) == b) return 1;
return 0;
}

int main()
{
int T;
cin >> T;
for(int ctr = 0;ctr < T;ctr++)
{
        long int n;
        long int ans = 0;
        cin >> n;
        long int k;
        for(long int i = 0;i < n;i++)
        {
                 cin >> k;
                 if(search(k) == 0){ ans++;a.push_back(k);}
        }
        cout << ans << endl;
        a.resize(0);
}
return 0;
}
2 Likes
2

Complexity of your is O(n*n) in the worst case per test case(when all the numbers are different).That’s why your solution got TLE’d

1 Like
3

you do not need to search elements if u use STL set instead of vector(cause it does not contain multiple elements with same value)

4

you only need to find out the number of distinct elements in the array. So you can first sort it out and then can find out the number of distinct elements. :slight_smile:

5

better u use hashing !!! it would be done in o(log n)

6

http://www.codechef.com/viewsolution/4348624
Here’s my solution. For the given constraints(N<=10^5) you can easily take a boolean array to count the distinct elements in the array by marking it whenever occured first time. You can avoid sorting here.