Re: Efficient Algorithm ?
Don't worry guys ! I found out the O (n) algorithm.
Re: Efficient Algorithm ?
Quote:
Originally Posted by
vsha041
Don't worry guys ! I found out the O (n) algorithm.
Lets compare solutions. :)
If there are N students there are N possible starting positions.
You need an array of N counters each representing a starting position.
By knowing a student's position at the table you also know which starting position satisfies this student's preference.
So you only have to visit each student once and increment the counter associated with his/her preference. Afterwards the starting position with the largest count is the one that satisfies most students.
Visiting each students is an O(N) process. Updating a counter is a table look-up so it's an O(1) process. This means the overall complexity will be O(N).
One can note that compared with the brute force O(N^2) algorithm this one has lower time complexity but at the cost of more memory (the N counters). In the original problem formulation N can be 10^5 at the most so this O(N) algorithm is still feasible.
Since the students don't have to be visited in any particular order they can be visited at the same time. It means the algorithm can be run in parallel and if there are N processors it will be O(1).
Re: Efficient Algorithm ?
Thanks nuzzle ! The O(n) algorithm I used is exactly same as yours. Thanks for your time.