Click here to Skip to main content
15,891,905 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
The code given in the website.
Smallest element repeated exactly ‘k’ times (not limited to small range) - GeeksforGeeks[^]
Which is the most efficient code out of these two?
Btw, both shows the correct output.

What I have tried:

/*https://www.geeksforgeeks.org/smallest-element-repeated-exactly-k-times-not-limited-small-range/
Smallest element repeated exactly ‘k’ times (not limited to small range)
*/
#include<bits/stdc++.h>
using namespace std;
int no_of_chars = 10;
int smallrepeat(int s[],int k, int n)
{
	int hash[no_of_chars] = {0};
	//Storing the frequency of occurances.
	for(int i=0;i<n;i++)
		hash[s[i]]++;
	//Finding smallest element repeated exactly 'k' times
	int repeatmore = 9;
	for(int i=0;i<n;i++){
		if(hash[s[i]] && (hash[s[i]] == k) && (s[i] < repeatmore))
			repeatmore = s[i];
	}

	return repeatmore;

}
int main()
{
	int s[] = { 2, 2, 1, 3, 1 };
	int n = sizeof(s)/sizeof(s[0]);
	int k = 2;
	cout<<"Smallest element repeated exactly ‘k’ times :"<<smallrepeat(s,k,n)<<endl;
}
Posted
Updated 3-Mar-19 23:42pm
Comments
Richard MacCutchan 3-Mar-19 3:58am    
Probably neither since the samples are too small. Set up some timing tests with large samples and you should easily find the answer.
Kohila G 3-Mar-19 4:05am    
So, a solution which takes less time is the most efficient? Both of them have the same time complexity : O(n).
Dave Kreskowiak 3-Mar-19 11:44am    
Not necessarily. Time isn't the only measure of "efficiency". What determines efficiency is going to be the circumstances under which the code must be run ro be "efficient". Is the requirement for the code going to be time? Is it going to be memory use? Is it going to be impact on CPU usage? Is it I/O dependent? Sharing resources? ...

The website version is likely to be the faster of the two but only by a very, very small margin because it has one less comparison within its loop. Yours has an additional check for a zero value of the hash array which seems unnecessary. Without that check the two would have nearly identical performance. The difference would probably be unmeasurable unless you use a very large data array and test multiple loops, like 100K or more.

In release mode, the subtle differences in the code will be mostly optimized away by the compiler. Those would be the .begin() and .end() parts of the for loop and the call to min which is usually inlined.
 
Share this answer
 
They are basically the same. Note your program doesn't produce the same output of the one on the webside if the element is not found.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900