Idea
- The key here is that any number is divisible by 4, if its last 2 digits are divisible by 4
- This can be proved by number theory, without considering the last 2 digits, all number is divisible by 4 because 25 * 4 = 100, and 9/3 = 3/3 + 6/2 = 1 + 2 = 3
- With this in mind, we can have a first loop to find all the single digit number that is divisible by 4
- Then we can find pair digits that are divisible by 4, if that pair is divisible by 4, we have the number of digits infront as the number of valid numbers too
- So in this case, the problem is statelessness, the current state is always the pair of digits, if the pair of digits is valid, all the digits are valid, we always only consider the current pair of digits aka the current state to find the number of valid numbers in this round
- The current state is the last 2 digits, if current state permits, then all the digits in-front can be counted as valid, 3 digits in-front == 3 extra valid numbers - x00, xx00, xxx00
Space & Time Analysis
- Space - O(1), we are only a variable to keep track of the answer
- Time - O(n), 2 linear loops
- miss on the number theory part
- Should think about the process and the constraint of obtaining a valid format (in this case it is what number gives us %4 == 0)
Codes