PROBLEM LINK:
Contest link
Problem link
Practice link
Author: HITK Chapter
Tester: Ankur Kayal
Editorialist: HITK Chapter
DIFFICULTY:
Easy
PREREQUISITES:
Strings, STL, Implementation.
PROBLEM:
Given a list of n words, you have to calculate its magic factor with the last word you encountered of the same length. Value of a word is the sum of values of each letter of the word. (For eg: a=1, b=2, etc) and Magic factor of 2 words having value v1 & v2 is = abs(v1−v2).
QUICK EXPLANATION:
Maintain a map and calculate the magic factor for every word encountered if a word of the same length is present in map.
EXPLANATION:
We can maintain a hash map for string lengths.
Every time we encounter a string whose size is n_1, we will check if a string of size n_1 is already available or not.
If there is an available string, we will calculate the diff factor of both strings and clear the map key of that particular length.
If there is no available string, we will store the value of that length in the map and move on.
Finally, we will print the sum of all magic factors calculated.
Time Complexity : O(nlog(n) + |s|) for each test case
The extra log(n) factor can be reduced if we use vector or unordered_map instead of map.