{"id":1510,"date":"2020-07-01T09:32:24","date_gmt":"2020-07-01T09:32:24","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1510"},"modified":"2022-03-23T23:22:18","modified_gmt":"2022-03-23T23:22:18","slug":"majority-votes","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/majority-votes\/","title":{"rendered":"Majority Votes"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Hashing<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array of size N<\/code>, which contains the voting ID's<\/code> 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<\/code> of candidate that can become monitor else return -1<\/code> if no one can become.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : A = [1, 3, 2, 2, 2]\n\nOutput : 2\n\nExplanation : 2 got 3 votes which is greater than half the strength of the class i.e. 5\/2 = 2.<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
BRUTE FORCE METHOD:<\/h4>\n
\n
    \n
  1. Run two loops, outer loop for selecting the voting ID<\/code> and inner loop for counting its frequency, after the inner loop ends check if the frequency is greater than Strength-of-class\/2<\/code>.  <\/li>\n
  2. If Yes<\/code> return this ID<\/code>, else check for all such ID's<\/code>. If no ID<\/code> wins the voting return -1<\/code>.<\/li>\n
  3. Time Complexity<\/code> of this solution is O(N^2)<\/code> and is not an efficient approach in terms of time taken.<\/li>\n<\/ol>\n<\/blockquote>\n
    EFFICIENT METHOD:<\/h4>\n
    \n
      \n
    1. \n
      The idea is to use Hashing<\/code>. While traversing the array of ID's<\/code> keep incrementing the count<\/code> of votes for that particular ID<\/code>.  <\/p>\n<\/li>\n
    2. \n
      If count<\/code> of any ID<\/code> becomes greater than Strength-of-class\/2<\/code>, simply return it. Else return -1<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      ILLUSTRATION:<\/h4>\n
      A = [1, 3, 2, 2, 2]\nhash[] \n\ni = 0\nhash[A[0]]++ => hash[1] = 1\n\ni = 1\nhash[A[1]]++ => hash[3] = 1\n\ni = 2\nhash[A[2]]++ => hash[2] = 1\n\ni = 3\nhash[A[3]]++ => hash[2] = 2\n\ni = 4\nhash[A[4]]++ => hash[2] = 3\nSince, 3 > 5\/2 \n\nTherefore, ID 2 with 3 votes wins the voting.<\/code><\/pre>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t