# What is a O(n) algorithm to solve this puzzle?

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, some last, etc). Everyone is seated randomly and cannot move from their position. How shall we compute the best starting position on the table to satisfy the most people?

I have an O(n^2) solution: See how many people would be satisfied having assumed each of the positions 1..n as start positions; then return the position that gave the maximum value.

• NB I will give a generous bounty ASAP if someone solves this Commented Mar 13, 2014 at 9:08
• That's not the way it works. You assign the bounty first, then maybe someone will be attracted to try the problem at all. Commented Mar 13, 2014 at 9:12
• Yes, I know - but I need to wait 2 days before I can do that Commented Mar 13, 2014 at 9:12
• Are people only satisfied if they speak exactly at the position they wanted to, or would they also be content if they speak near their position (e.g. if someone wants to go first, but has to go second, that would be suboptimal but still better than going last?)
– amon
Commented Mar 13, 2014 at 9:13
• @amon They are "satisfied" if and only if they are given their exact preference. 1 space away might as well be n/2 away :) Commented Mar 13, 2014 at 9:14

A fairly simple O(n) algorithm exists:

Let `pos` be an array so that if the person at seat `i` wants to speak as `n`-th, we have an entry `pos[i] = n`. Where the numbering of the seats starts is irrelevant. Both `i` and `n` start counting with zero.

The difference `i - pos[i]` is the seat where the round would have to start for the person at seat `i` to be satisfied. We count the satisfied persons per start position in a `satisfied` array. We can then find the maximum of that array, the index of the maximum is the seat where the round should start for maximum satisfaction.

Java example:

``````int findBestStart(int[] pos) {
// ask each seat where they'd like to start
int[] satisfied = new int[pos.length];
for (int i = 0; i < pos.length; i++) {
int start = i - pos[i]
if (start < 0) start += pos.length;
satisfied[start]++;
}

// find where most would like to start
int bestSeat = -1;
int bestSatisfied = -1;
for (int i = 0; i < satisfied.length; i++) {
if (satisfied[i] > bestSatisfied) {
bestSeat = i;
bestSatisfied = satisfied[i];
}
}

return bestSeat;
}
``````
• Thank you, sir. Very nice. I will throw over a bounty in 2 days Commented Mar 13, 2014 at 9:32
• @d'alar'cop oh, there is no need for a bounty, I have enough rep as it is.
– amon
Commented Mar 13, 2014 at 9:34
• Understood. Glad you do it for the love of it. All the best Commented Mar 13, 2014 at 9:35
• I need to verify, but I think this is the same as the O(n^2) algorithm with just one pass. Therefore while the maximum is likely a good approximation, it probably isn't the maximum.
– Neil
Commented Mar 13, 2014 at 10:03

If each person knows exactly what order he wants to go in and the seating order is constant, then each person knows what starting position he wants the speaking to start at. This way, you can calculate how many people want speaking start at specific points, which is O(n) in complexity if you the preferred position as index into array.

• +1 Thanks! I know you were first... and the answers are equivalent in concept... but amon gave a more formal response with some code. Commented Mar 13, 2014 at 9:31
• +1 This somehow explained it to me better than the answer with the code
– dj18
Commented Mar 13, 2014 at 19:14