PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Brute Force
PROBLEM:
Given two strings of digits denoting two consecutive numbers, with some digits missing. Find all possible numbers that they can possibly denote.
QUICK EXPLANATION:
Iterate through all possible numbers and check whether it works.
EXPLANATION:
Since the given constraints is small, it is possible to iterate through all possible numbers with the given number of digits. It remains to have a function that checks whether each number matches a string of digits.
For subtask 1, this is fairly easy, since the number only consists of 1 digit, so we can just check directly.
However, for subtask 2, the number can have 5 digits. We need to extract the digits of the number to compare it with the given string of digits. How do we do that? The easiest way is to keep extracting the last digit from the number, and divide it by 10. If we keep doing this, we can get all the digits.
For example, let’s say we want to get the digits of 2346. We extract the last digit (which can be done by taking its remainder modulo 10), so in this case we get 6, and divide the number by 10 (and taking the integer part of it), so we get 234. We repeat this process and extract the digit 4, and divide it by 10, which gives 23. Repeating this process two more times gives us the digits 6, 4, 3, 2. Now, we just have to reverse the order of the digits and we get 2, 3, 4, 6.
After getting all the digits, we can compare the digits with the given string directly and determine if the number matches the string.
Another way to get all the digits is to use builtin functions in your chosen language. If you’re aware of them (or googled them), it will simplify your implementation.
A similar problem which can be solved using this trick can be found here.
There is a small but nasty trap : The pair (99999, 100000) (and similarly (9, 10), (99, 100), …) are invalid because they have different number of digits. Also, be careful to not print the pair (0, 1). (this was explicitly stated in the problem statement)
Time Complexity : O(N \cdot \log{N}), where N is the maximum possible number that can be formed, which is 99999 in this case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.