Find who won the election based on given voting system
Given an array of pairs arr[][] of the form {X, Y} such that each arr[i] represents the time X at which the candidate with candidate ID Y was voted and an array of queries query[] consisting of M positive integers, the task for each query Q[i] is to find the winning candidate ID at that time Q[i] of voting.
Note: In case, there are 2 candidates with the same number of votes K at a given time, then print the candidate who got those votes first.
Examples:
Input: arr[] = {{1, 2}, {2, 2}, {4, 1}, {5, 5}, {7, 1}, {11, 1}}, query[] = {2, 8, 12}
Output: 2 2 1
Explanation:
For query[0] = 2, at time 2, the candidate with candidateID = 2 has got the maximum votes.
For query[1] = 8, at time 8, the candidates with candidateID’s = 2 and 1 have got the maximum votes i.e, 2 but since candidate with ID 2 got those before so the answer is 2.
For query[2] = 12, at time 12, the candidate with candidateID = 1 has got the maximum votes i.e, 3.Input: arr[] = {{1, 1}}, query[] = { 1 }
Output: 1
Approach: The given problem can be solved by precomputing the winner at each coming time interval in the array arr[] and store it in another array, say Ans[] in the form of {timeInterval, winnerCandidateID} and then for each query query[i] perform the Binary Search on the array Ans[] to get the winning Candidate at time query[i]. Follow the steps below to solve the problem:
- Initialize a vector, say Ans[] that stores the winner at each incoming time interval arr[i].first.
- Initialize an unordered map, say Map[] that stores the frequency of the candidate’s ID at each incoming time interval.
- Initialize a pair, say previous[] that keeps the track of the winning candidate.
- Push the first pair in the vector Ans[] and mark that as the previous.
- Iterate over the range [1, N – 1] using the variable i and perform the following steps:
- Increment the frequency of the current candidate arr[i].second by 1 in the map Map.
- If the current candidate wins till now, then update the pair previous.
- Insert the previous in the vector Ans[].
- Iterate over the range [0, M) using the variable i and perform the following steps:
- For each query, perform a binary search on the vector of pairs Ans[] to find the winning candidate.
- Perform the binary search on the time i.e, the first value of the vector of pairs Ans[] and find the largest value which is less than equal to query[I], and print the corresponding candidateID.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include "bits/stdc++.h" using namespace std; // Function to perform binary search // to find the candidate with most votes // for a particular time int binarySearch(vector<pair< int , int > >& Ans, int low, int high, int value) { // Base Cases if (value <= Ans[low].first) return Ans[low].second; if (value >= Ans[high].first) return Ans[high].second; int winningCandidate; while (low <= high) { // Find the mid int mid = low + (high - low) / 2; // If the value at mid is the // result if (Ans[mid].first == value) { winningCandidate = Ans[mid].second; break ; } // Update the ranges else if (Ans[mid].first < value) { winningCandidate = Ans[mid].second; low = mid + 1; } else { high = mid - 1; } } return winningCandidate; } // Function to find the winner for each query void findWinner(pair< int , int > arr[], int N, int query[], int M) { // Map to store the frequency unordered_map< int , int > Map; // Stores the winning candidate till // a particular time vector<pair< int , int > > Ans; // Starting Reference pair< int , int > previous = { arr[0].first, arr[0].second }; Ans.push_back(previous); Map[arr[0].second]++; // Iterate over the range for ( int i = 1; i < N; i++) { // Increase the frequency Map[arr[i].second]++; // Update the reference if another // candidate gets more votes than // the one considered if (Map[arr[i].second] > Map[previous.second]) { previous.second = arr[i].second; } previous.first = arr[i].first; // Push into the vector Ans.push_back(previous); } // Iterate over the range for ( int i = 0; i < M; i++) { cout << binarySearch(Ans, 0, N - 1, query[i]) << ' ' ; } } // Driver Code int main() { pair< int , int > arr[] = { { 1, 2 }, { 2, 2 }, { 4, 1 }, { 5, 5 }, { 7, 1 }, { 11, 1 } }; int query[] = { 2, 8, 12 }; int N = 6; int M = 3; findWinner(arr, N, query, M); return 0; } |
Java
import java.util.*; public class Main { static class Pair<T, U> { private T key; private U value; public Pair(T key, U value) { this .key = key; this .value = value; } public T getKey() { return key; } public U getValue() { return value; } } public static int binarySearch(List<Pair<Integer, Integer>> Ans, int low, int high, int value) { // Base Cases if (value <= Ans.get(low).getKey()) { return Ans.get(low).getValue(); } if (value >= Ans.get(high).getKey()) { return Ans.get(high).getValue(); } int winningCandidate = 0 ; while (low <= high) { // Find the mid int mid = low + (high - low) / 2 ; // If the value at mid is the // result if (Ans.get(mid).getKey() == value) { winningCandidate = Ans.get(mid).getValue(); break ; } // Update the ranges else if (Ans.get(mid).getKey() < value) { winningCandidate = Ans.get(mid).getValue(); low = mid + 1 ; } else { high = mid - 1 ; } } return winningCandidate; } public static void findWinner(Pair<Integer, Integer>[] arr, int N, int [] query, int M) { // Map to store the frequency Map<Integer, Integer> Map = new HashMap<>(); // Stores the winning candidate till // a particular time List<Pair<Integer, Integer>> Ans = new ArrayList<>(); // Starting Reference Pair<Integer, Integer> previous = new Pair<>(arr[ 0 ].getKey(), arr[ 0 ].getValue()); Ans.add(previous); Map.put(arr[ 0 ].getValue(), 1 ); // Iterate over the range for ( int i = 1 ; i < N; i++) { // Increase the frequency Map.put(arr[i].getValue(), Map.getOrDefault(arr[i].getValue(), 0 ) + 1 ); // Update the reference if another // candidate gets more votes than // the one considered if (Map.get(arr[i].getValue()) > Map.get(previous.getValue())) { previous = new Pair<>(arr[i].getKey(), arr[i].getValue()); } // Push into the list Ans.add(previous); } // Iterate over the range for ( int i = 0 ; i < M; i++) { System.out.print(binarySearch(Ans, 0 , N - 1 , query[i]) + " " ); } } public static void main(String[] args) { Pair<Integer, Integer>[] arr = new Pair[ 6 ]; arr[ 0 ] = new Pair<>( 1 , 2 ); arr[ 1 ] = new Pair<>( 2 , 2 ); arr[ 2 ] = new Pair<>( 4 , 1 ); arr[ 3 ] = new Pair<>( 5 , 5 ); arr[ 4 ] = new Pair<>( 7 , 1 ); arr[ 5 ] = new Pair<>( 11 , 1 ); int [] query = { 2 , 8 , 12 }; int N = 6 ; int M = 3 ; findWinner(arr, N, query, M); } } |
Python3
# Python 3 program for the above approach from collections import defaultdict # Function to perform binary search # to find the candidate with most votes # for a particular time def binarySearch(Ans, low, high, value): # Base Cases if (value < = Ans[low][ 0 ]): return Ans[low][ 1 ] if (value > = Ans[high][ 0 ]): return Ans[high][ 1 ] while (low < = high): # Find the mid mid = low + (high - low) / / 2 # If the value at mid is the # result if (Ans[mid][ 0 ] = = value): winningCandidate = Ans[mid][ 1 ] break # Update the ranges elif (Ans[mid][ 0 ] < value): winningCandidate = Ans[mid][ 1 ] low = mid + 1 else : high = mid - 1 return winningCandidate # Function to find the winner for each query def findWinner(arr, N, query, M): # Map to store the frequency Map = defaultdict( int ) # Stores the winning candidate till # a particular time Ans = [] # Starting Reference previous = [arr[ 0 ][ 0 ], arr[ 0 ][ 1 ]] Ans.append([previous[ 0 ], previous[ 1 ]]) Map [arr[ 0 ][ 1 ]] + = 1 # Iterate over the range for i in range ( 1 , N): # Increase the frequency Map [arr[i][ 1 ]] + = 1 # Update the reference if another # candidate gets more votes than # the one considered if ( Map [arr[i][ 1 ]] > Map [previous[ 1 ]]): previous[ 1 ] = arr[i][ 1 ] previous[ 0 ] = arr[i][ 0 ] # Push into the vector Ans.append([previous[ 0 ], previous[ 1 ]]) # Iterate over the range for i in range (M): print (binarySearch( Ans, 0 , N - 1 , query[i]), end = ' ' ) # Driver Code if __name__ = = "__main__" : arr = [[ 1 , 2 ], [ 2 , 2 ], [ 4 , 1 ], [ 5 , 5 ], [ 7 , 1 ], [ 11 , 1 ]] query = [ 2 , 8 , 12 ] N = 6 M = 3 findWinner(arr, N, query, M) # This code is contributed by ukasp. |
C#
using System; using System.Collections.Generic; // Generic pair class definition public class Pair<T, U> { // Class members private T key; private U value; // Constructor public Pair(T key, U value) { this .key = key; this .value = value; } // Getter methods public T Key { get { return key; } } public U Value { get { return value; } } } class GFG { // This function performs binary search operation public static int BinarySearch(List<Pair< int , int > > Ans, int low, int high, int value) { // Base Cases if (value <= Ans[low].Key) { return Ans[low].Value; } if (value >= Ans[high].Key) { return Ans[high].Value; } int winningCandidate = 0; while (low <= high) { // Find the mid int mid = low + (high - low) / 2; // If the value at mid is the result if (Ans[mid].Key == value) { winningCandidate = Ans[mid].Value; break ; } // Update the ranges else if (Ans[mid].Key < value) { winningCandidate = Ans[mid].Value; low = mid + 1; } else { high = mid - 1; } } return winningCandidate; } public static void FindWinner(Pair< int , int >[] arr, int N, int [] query, int M) { // Dictionary to store the frequency Dictionary< int , int > Map = new Dictionary< int , int >(); // List to store the winning candidate till a // particular time List<Pair< int , int > > Ans = new List<Pair< int , int > >(); // Starting Reference Pair< int , int > previous = new Pair< int , int >(arr[0].Key, arr[0].Value); Ans.Add(previous); Map[arr[0].Value] = 1; // Iterate over the range for ( int i = 1; i < N; i++) { // Increase the frequency if (Map.ContainsKey(arr[i].Value)) { Map[arr[i].Value]++; } else { Map[arr[i].Value] = 1; } // Update the reference if another candidate // gets more votes than the one considered if (Map[arr[i].Value] > Map[previous.Value]) { previous = new Pair< int , int >(arr[i].Key, arr[i].Value); } // Add to the list Ans.Add(previous); } // Iterate over the range for ( int i = 0; i < M; i++) { Console.Write( BinarySearch(Ans, 0, N - 1, query[i]) + " " ); } } // Driver code public static void Main( string [] args) { Pair< int , int >[] arr = { new Pair< int , int >(1, 2), new Pair< int , int >(2, 2), new Pair< int , int >(4, 1), new Pair< int , int >(5, 5), new Pair< int , int >(7, 1), new Pair< int , int >(11, 1) }; int [] query = { 2, 8, 12 }; int N = 6; int M = 3; FindWinner(arr, N, query, M); } } // This code is contributed by phasing17. |
Javascript
// JS program to implement the approach // Function to perform binary search // to find the candidate with most votes // for a particular time function binarySearch(Ans, low, high, value) { // Base Cases if (value <= Ans[low][0]) { return Ans[low][1]; } if (value >= Ans[high][0]) { return Ans[high][1]; } while (low <= high) { // Find the mid let mid = low + Math.floor((high - low) / 2); // If the value at mid is the result if (Ans[mid][0] === value) { return Ans[mid][1]; } // Update the ranges if (Ans[mid][0] < value) { low = mid + 1; winningCandidate = Ans[mid][1]; } else { high = mid - 1; } } return winningCandidate; } // Function to find the winner for each query function findWinner(arr, N, query, M) { // Map to store the frequency let Map = {}; // Stores the winning candidate till // a particular time let Ans = []; // Starting Reference let previous = [arr[0][0], arr[0][1]]; Ans.push([previous[0], previous[1]]); if (!Map[arr[0][1]]) { Map[arr[0][1]] = 0; } Map[arr[0][1]] += 1; // Iterate over the range for (let i = 1; i < N; i++) { // Increase the frequency if (!Map[arr[i][1]]) { Map[arr[i][1]] = 0; } Map[arr[i][1]] += 1; // Update the reference if another // candidate gets more votes than // the one considered if (Map[arr[i][1]] > Map[previous[1]]) { previous[1] = arr[i][1]; } previous[0] = arr[i][0]; // Push into the vector Ans.push([previous[0], previous[1]]); } // Iterate over the range for (let i = 0; i < M; i++) { process.stdout.write(binarySearch(Ans, 0, N - 1, query[i]) + " " ); } } // Driver Code const arr = [[1, 2], [2, 2], [4, 1], [5, 5], [7, 1], [11, 1]]; const query = [2, 8, 12]; const N = 6; const M = 3; // Function call findWinner(arr, N, query, M); // This code is contributed by phasing17 |
2 2 1
Time Complexity: O(max(N, M*log(N)))
Auxiliary Space: O(N)
Contact Us