Barbara Bennett's Wild Numbers
InterviewTime limit1sMemory limit128 MB
Given a wild number W with digit and ? positions and a same-length number X, count the length-n digit strings matching W that are strictly greater than X.
- Level
Medium4 of 10
- Topics
- Combinatorics, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
A wild number is a string made of digits and question marks, such as 36?1?8. A number matches a wild number if they have the same length and every non-question-mark character of equals the character in the same position of (a question mark may be replaced by any single digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, and 36128 do not. Given a wild number and a number of the same length , count how many length- digit strings match and are strictly greater than when the two are compared as numbers of the same length. Leading zeros are allowed.
Input
The input contains several test cases. Each test case consists of two lines of equal length: the first line holds a wild number , and the second line holds a number . Each line has length between and . The input ends with a line containing a single # character.
Output
For each test case, print on its own line the number of length- numbers that match and are greater than , where is the common length of and .