EVM Machine - Hashing - Post Class | Newton school assignment
Problem Statement During the elections, Bob is in charge of conducting voting in his village, but the EVM system malfunctioned, and there was a long line of voters waiting outside to vote. The following is how the Advanced EVM Machine works. Each time when a voter scans his VoterId Card and votes for the party of his choice, the Voter's id and Party Name are registered in the background, and if the same voter votes again, the EVM does not capture his vote, then the vote is skipped and the vote given the first time is used. Now that you are Bob's best mate, you can't bear to see him in such a strained situation when outside voters are being very aggressive and screaming at him. Can you easily write a piece of code to save your friend's life while Bob is busy calming down the outside situation? Input The number N (1 ≤ N ≤ 1e5) appears on the first line. The queries to the machine are included in the next n lines. Each request consists of two strings and is written on a non- empty line. The first string is an Voter Card Id, and the second string is the Party Name, all of which are atmost 32 characters long both upper case and lower case possible. Constraints 1 ≤ N ≤ 100000 1 ≤ Voter Id length ≤ 40 1 ≤ PartyName length ≤ 32 Output Output a single line indicating which party has won and by how many votes. In case of a draw between parties print all the parties with the same winning vote, in lexographically increasing order on basis of Party Name. Example Sample Input 4 12678345 BJP 57891082 Congress 12678345 AAP 65489 TMC Sample Output BJP 1 Congress 1 TMC 1 Explanation : As Winning Parties here as BJP, Congress, TMC with 1 vote(s) each, but AAP vote is not considered because the same VoterId - 12678345 has done a vote again.
Here is a solution in
Java:import java.util.*; class Main { public static void main(String[] args) { // Read input Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); // consume newline Map<String, Integer> votes = new HashMap<>(); // store party votes Set<String> voterIds = new HashSet<>(); // store voter IDs for (int i = 0; i < n; i++) { String[] line = sc.nextLine().split(" "); String voterId = line[0]; String party = line[1]; if (!voterIds.contains(voterId)) { // check if voter has already voted voterIds.add(voterId); // add voter ID to set votes.put(party, votes.getOrDefault(party, 0) + 1); // increment party vote count } } // Find the party with the most votes int maxVotes = 0; List<String> winners = new ArrayList<>(); for (Map.Entry<String, Integer> entry : votes.entrySet()) { if (entry.getValue() > maxVotes) { maxVotes = entry.getValue(); winners.clear(); // clear previous winners winners.add(entry.getKey()); } else if (entry.getValue() == maxVotes) { winners.add(entry.getKey()); } } // Print the winner(s) if (winners.size() == 1) { System.out.println(winners.get(0) + " " + maxVotes); } else { // sort parties in lexicographic order Collections.sort(winners); for (String party : winners) { System.out.println(party + " " + maxVotes); } } }
This solution uses a HashMap to store the number of votes for each party, and a HashSet to store the voter IDs. For each vote, it checks if the voter ID has already been added to the set. If not, it adds it to the set and increments the vote count for the party. After all votes have been processed, it finds the party with the most votes and prints the result. If there is a tie, it prints all of the parties with the same number of votes in lexicographic order.
import java.util.*;
This line imports the java.util package, which contains several useful classes such as Scanner and HashMap.
class Main {
public static void main(String[] args) {
// Read input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); // consume newline
Map<String, Integer> votes = new HashMap<>(); // store party votes
Set<String> voterIds = new HashSet<>(); // store voter IDs
This code declares the main method, which is the entry point of the program. It creates a Scanner object to read input from the standard input stream, and reads the number of votes n. It then consumes the newline character after n.
Next, it creates a HashMap to store the number of votes for each party, and a HashSet to store the voter IDs.
for (int i = 0; i < n; i++) {
String[] line = sc.nextLine().split(" ");
String voterId = line[0];
String party = line[1];
if (!voterIds.contains(voterId)) { // check if voter has already voted
voterIds.add(voterId); // add voter ID to set
votes.put(party, votes.getOrDefault(party, 0) + 1); // increment party vote count
}
}
This loop reads the voter IDs and party names from the input and processes each vote. It checks if the voter ID has already been added to the set. If not, it adds it to the set and increments the vote count for the party in the votes map.
//Find the party with the most votes int maxVotes = 0;
List<String> winners = new ArrayList<>();
for (Map.Entry<String, Integer> entry : votes.entrySet()) {
if (entry.getValue() > maxVotes) {
maxVotes = entry.getValue();
winners.clear(); // clear previous winners
winners.add(entry.getKey());
} else if (entry.getValue() == maxVotes) {
winners.add(entry.getKey());
}
}This code finds the party with the most votes. It iterates through the entries in the votes map and keeps track of the maximum number of votes and the parties with that number of votes. If it finds a party with more votes than the current maximum, it updates the maximum and clears the list of winners. If it finds a party with the same number of votes as the current maximum, it adds it to the list of winners.
// Print the winner(s)
if (winners.size() == 1) {
System.out.println(winners.get(0) + " " + maxVotes);
} else {
// sort parties in lexicographic order
Collections.sort(winners);
for (String party : winners) {
System.out.println(party + " " + maxVotes);
.png)
.png)
