Question

Using Java,

Given an array A[0 ... n-1], where each element of the array represent a vote in the election. Assume that each vote is given as an integer representing the ID of the chosen candidate. Can you determine who wins the election? What is the complexity of your solution? Hint: it is similar to finding the element that is repeated the maximum number of times.

Answer 1

  
import java.io.*;
  
class Main{

static void findWinner(int arr[], int n)
{
int maxCount = 0;
int index = -1; // sentinels
for(int i = 0; i < n; i++)
{
int count = 0;
for(int j = 0; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
  
// update maxCount if count of
// current element is greater
if(count > maxCount)
{
maxCount = count;
index = i;
}
}
  
// if maxCount is greater than n/2
// return the corresponding element
if (maxCount > n/2)
System.out.println ("Candidate with id:"+arr[index]+" won the election");
  
else
System.out.println ("It's a tie between candidates");
} //complexity O(n*n)
  
// Driver code
public static void main (String[] args) {
  
int arr[] = {1, 1, 2, 1, 3, 5, 1};
int n = arr.length;
  
// Function calling
findWinner(arr, n);
}

}

output:

Candidate with id:1 won the election