PROBLEM LINK:
Author:
Aditi Agarwal
Tester:
Siddharth Sahai
DIFFICULTY:
EASY
PREREQUISITES:
Sorting
PROBLEM:
When a person enters or exits a library, he enters his name in a register. By looking at the list of names in the register, find out how many people are there in the library.
EXPLANATION:
For every name, we find its frequency, i.e. how many times it has appeared in the list. If a person’s name’s frequency is even, then he/she is not in the library, otherwise he/she is in the library.
To find frequencies, sort the list of names in lexicographic order. Then all same names will be consecutive in the array and frequency can be easily calculated by comparing every pair of 2 consecutive names.
For the program to be within time limit, sorting has to be done in O(n log(n)) time. Usually standard library functions can sort with an average time complexity of O(n log(n)).