PROBLEM LINK:
Author: Sergey Kulik
Tester: Roman Furko
Editorialist: Balajiganapathi Senthilnathan
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic string
PROBLEM
For each number, you have to count the number of times the digit 4 occurs in it.
QUICK EXPLANATION
Input the number as a string and count the number of times the character ‘4’ occurs in it.
EXPLANATION
We may be tempted to input the number as an int, but this is really a string related task. We have to count the number of times a particular character appears in the string. So, taking the input as a string helps us avoid all the complicated stuff we will have to do if we input as a number.
We just have to loop through all characters of the string and if it is ‘4’, increment the answer.
It is also instructive to see how we can solve this if we treat the input as a number.
Say we have a number x = 12345. How can we extract its digits? Observe that we can easily get the rightmost digit(unit’s place) - if we divide x by 10 and take the reminder, it will be the rightmost digit. Further, the quotient we get is the rest of the number. For example, 12345 = 1234 * 10 + 5. So we get both the unit’s place digit and the rest of the number. Now to get the next digit, we continue in the same fashion. When should we stop? Suppose x is a single digit, say x = 1. Now the quotient after dividing by 10 is 0, and we can stop since there are no more digits to process.
Pseudocode:
ans = 0 while x > 0: remainder = x % 10 quotient = x / 10 if remainder == 4 ans++ x = quotient
Complexity
The number of times the while loop will run is equal to the number of digits. Say d is the number of digits, the complexity will therefore be O(d). Also, if we treat the input as integer, we can see that d = \lceil log_{10} n \rceil. So, the complexity will be \mathcal{O}(log n).