Majority Votes

CONCEPTS USED:

Hashing

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given an array of size N, which contains the voting ID's of students that have stood up for the elections for class monitor, the candidate with votes greater than half the strength of the class will become monitor, find the ID of candidate that can become monitor else return -1 if no one can become.

For Example:

Input : A = [1, 3, 2, 2, 2]

Output : 2

Explanation : 2 got 3 votes which is greater than half the strength of the class i.e. 5/2 = 2.

SOLVING APPROACH:

BRUTE FORCE METHOD:

1. Run two loops, outer loop for selecting the voting ID and inner loop for counting its frequency, after the inner loop ends check if the frequency is greater than Strength-of-class/2.
2. If Yes return this ID, else check for all such ID's. If no ID wins the voting return -1.
3. Time Complexity of this solution is O(N^2) and is not an efficient approach in terms of time taken.

EFFICIENT METHOD:

1. The idea is to use Hashing. While traversing the array of ID's keep incrementing the count of votes for that particular ID.

2. If count of any ID becomes greater than Strength-of-class/2, simply return it. Else return -1.

ILLUSTRATION:

A = [1, 3, 2, 2, 2]
hash[] 

i = 0
hash[A[0]]++ => hash[1] = 1

i = 1
hash[A[1]]++ => hash[3] = 1

i = 2
hash[A[2]]++ => hash[2] = 1

i = 3
hash[A[3]]++ => hash[2] = 2

i = 4
hash[A[4]]++ => hash[2] = 3
Since, 3 > 5/2 

Therefore, ID 2 with 3 votes wins the voting.

SOLUTIONS:

#include <stdio.h>

int main()
{
  int t; scanf("%d", &t);
  while(t--){
    int n; scanf("%d", &n);

    //storing frequency of votes in hash array
    int hash[1000000] = {0};
    int arr[n];
    int winner = -1;
    for(int i=0; i<n; i++){
      scanf("%d", &arr[i]);
      hash[arr[i]]++;

      /* if frequency of votes becomes greater than half 
         of total votes, this element is our winner */
      if(hash[arr[i]] > n/2)
        winner = arr[i];
    }
    printf("%d\n", winner);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t; cin>>t;
  while(t--){
    int n; cin>>n;

    //storing frequency of votes in hash array
    int hash[1000000] = {0};
    int arr[n];
    int winner = -1;
    for(int i=0; i<n; i++){
      cin>>arr[i];
      hash[arr[i]]++;

      /* if frequency of votes becomes greater than half 
         of total votes, this element is our winner */
      if(hash[arr[i]] > n/2)
        winner = arr[i];
    }
    cout<<winner<<"\n";
  }

  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
     int t = sc.nextInt();
    while(t != 0){
      int n = sc.nextInt();

      //storing frequency of votes in hash array
      int hash[] = new int[1000000];
      int arr[] = new int[n];
      int winner = -1;
      for(int i=0; i<n; i++){
        arr[i] = sc.nextInt();
        hash[arr[i]]++;

        /* if frequency of votes becomes greater than half 
           of total votes, this element is our winner */
        if(hash[arr[i]] > n/2)
          winner = arr[i];
      }
      System.out.println(winner);
      t--;
    }
  }
}

This article tried to discuss Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out .