PROBLEM LINK:
Author: Bhushan Khanale
Tester: D Teja Vardhan Reddy
Editorialist: Bhushan Khanale
DIFFICULTY:
EASY
PREREQUISITES:
Prefix array, hexadecimal number system.
PROBLEM:
The problem asks you ti find number of alphabets you can get through hexadecimal
numbers in a given range [L, R].
QUICK EXPLANATION:
The solution to the problem is very simple if you know about hexadecimal number
systems. You can read about it
here.
Then convert all numbers in the range to hexadecimal numbers and count the
number of alphabets you get. Use prefix array to answer all testcases.
EXPLANATION:
First to convert decimal number into hexadecimal number you need to divide
the number by 16 (since this is base 16), and keep recording the remainder.
Here as we are only concerned about the alphabets, we need to count the
remainders which are \geq 10. This is because in hexadecimal number system
the alphabets represent the numbers in the range [10, 15]. Hence the decimal
numbers in that range will be represented by hexadecimal numbers [A, F].
Since there are mutiple testcases, we only need to calculate this once and use
prefix array which would keep count of total alphabets at every index. Then we
can process each query with O(1).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.