I think all people have issues with time limit exceed. so i will write a small blog about the frequency array which is the solution of 70% of the time limit exceed error.
What is the frequency array? frequency array is an array that saves how many times this value repeated like i have input: 1 2 3 1 1 5 the frequency array will have values of: {0,3,1,1,0,1} when you use it, the time decreases from 2 seconds to maybe 400ms in 100 000 inputs (2 seconds if you used nested loop the know the values).
How to write it as a code? first we have an array of size n(100 000) and we get its elements from a loop like:
int n; cin >> n; int arr[n]; int freq[100001] = {0}; for(int i = 0; i < n; i++) { cin >> arr[i]; //here we use frequency array freq[arr[i]]++; // this makes the place of the number increases from 0 to 1 and it's the count for the first loop }
What is the benefit of it? - You can search easily with just the number if it's more than 0 so it exists. - time is almost the quarter of the nested loops time. more and more of benefits you can search for them. I hope my blog about the frequency array makes your code more efficient and increases your knowledge. See you in another blog <3