PROBLEM LINK:
Authors: Jaub Safin
Testers: Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Praveen Dhinwa
DIFFICULTY:
Cakewalk
PREREQUISITES:
String processing
PROBLEM:
You have a clock which ticks H hours. It ticks M minutes in an hour. Let h:m denote the time shown by the clock at some instant, where h is an integer without leading zeros denoting the current hour and M denoting the current minute. Note that both h and m don’t have leading zeros.
We define a duration h:m good if both h and m contain a single digit in their decimal representation. e.g. 2:22 is good where 2:3 is bad.
Note that the duration 02:22 is also good as it will be represented as 2:22 when we write h without leading zeros.
Find out number of good durations h:m such that 0 \leq h < H, 0 \leq m < M.
QUICK EXPLANATION:
As values of H and M (\leq 100) are very small. We can simply use a brutefore approach.
Let us iterate over hour h from 0 to H - 1 and m from 0 to M-1, we represent h and m as strings and check whether both the strings are made of a unique character or not.
EXPLANATION:
As stated in previous section, we can iterate over h from 0 to H - 1 and m from 0 to M-1, we represent h and m as strings and check whether both the strings are made of some unique character or not.
Pseudo Code
int ans = 0;
for (int h = 0; h < H; h++) {
for (int m = 0; m < M; m++) {
if (isGood(toString(h) + toString(m))) {
ans++;
}
}
}
Now, let us learn few tricks of how to convert an integer into a string.
General method (not specific to any language)
We extract the digits of the number one by one and append to our answer string. See the code below.
string ans = ""
while (n > 0) {
ans += (char) (n % 10 + '0');
n /= 10;
}
reverse(ans.begin(), ans.end())
C specific method
We can use itoa() function for converting an integer to a string.
char * s = itoa(n)
C++ specific methods
In C++ 11, you can use to_string method.
string s = to_sring(n)
You can also make use of string streams.
ostringstream os;
os << n;
string s = os.str()
Java specific methods
String ans = String.valueOf(n);
Checking whether all the digits of a string are equal or not
We can iterate over each character of the string and check whether it is equal to previous or not. If all the digits of the string are not equal, then there would be a character whose previous charater is not equal to that.
for (int i = 1; i < s.size(); i++) {
if (s[i] != s[i - 1]) {
return false;
}
}
return true;
Alternatively, you can insert the characters into a set and check whether size of set is one or not.
set<char> st;
for (int i = 0; i < s.size(); i++) {
st.insert(s[i]);
}
return st.size() == 1;
Time Complexity:
We spend \mathcal{O}(H \cdot M) for iterating over h and m, then converting h and m to strings and the later processing requires operations equal to number of digits in both h and m. As we note that h and m can not be larger than 100. So, it can be at max 3 + 3 = 6, which is \mathcal{O}(1).
So total time will be \mathcal{O}(H \cdot M) which is around 10^4 operations for each test case. There are around 50 test cases. So, we will make around 5 * 10^5 operations overall which will easily run under 1 secs as normally we have around 3 * 10^8 operations in a second.