CODEWITHSUNDEEP
algorithm
bollock1
bollock1

Reputation: 85

Efficient divide-and-conquer algorithm

At a political event, introducing 2 people determines if they represent the same party or not. Suppose more than half of the n attendees represent the same party. I'm trying to find an efficient algorithm that will identify the representatives of this party using as few introductions as possible.

A brute force solution will be to maintain two pointers over the array of attendees, introducing n attendees to n-1 other attendees in O(n2) time. I can't figure out how to improve on this.

Edit: Formally,

You are given an integer n. There is a hidden array A of size n, such that more than half of the values in A are the same. This array represents the party affiliation of each person.

You are allowed queries of the form introduce(i, j), where i≠j, and 1 <= i, j <= n, and you will get a boolean value in return: You will get back 1, if A[i] = A[j], and 0 otherwise.

Output: B ⊆ [1, 2. ... n] where |B| > n/2 and the A-value of every element in B is the same.

Hopefully this explains the problem better.

Upvotes: 0

Views: 385

Answers (1)

CodeChef
CodeChef

Reputation: 175

This can be done in O(n) introductions using the Boyer–Moore majority vote algorithm.

Consider some arbitrary ordering of the attendees: A_1, A_2, ..., A_n. In the algorithm, you maintain a 'stored element', denoted by m. Whenever the algorithm wants to check if the current element (x) is same as the stored element or not, you introduce those two people and increment or decrement the counter accordingly. The stored element at the end will be a member of the majority party. Then, you can do another pass over all the other n - 1 people, and introduce each of them to this known person and hence find all the members of the majority party.

Thus, the total number of introductions is O(n).

Upvotes: 2

Related Questions