Count Good Numbers up to a Limit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Count Good Numbers up to a Limit
A positive integer is **good** when all of the following hold:
1. Its decimal representation contains no digit `0`.
2. No digit appears more than once.
3. No internal digit is strictly smaller than both adjacent digits. In digits `... a, b, c ...`, the pattern `a > b < c` is forbidden. The first and last digits have only one neighbor and are not checked by this rule.
Given `m`, return the number of good integers `x` such that `1 <= x <= m`.
Implement:
```python
def solve(m: int) -> int:
...
```
## Constraints
- `1 <= m <= 10^18`
- A good integer has at most nine digits because only digits `1` through `9` are allowed and cannot repeat.
## Examples
```text
m = 9 -> 9
m = 10 -> 9
m = 21 -> 18
```
For `m = 21`, the good values are `1..9`, `12..19`, and `21`; `10`, `11`, and `20` are invalid.
Overview: Count positive integers up to a large limit whose decimal digits are nonzero, unique, and contain no internal valley pattern. The task combines an upper bound of 10^18 with a nine-digit structural limit and requires careful handling of prefixes and boundary values.
Read the full Google Software Engineer interview experience this question came from
Implement solve(m_decimal), where m_decimal is the exact decimal string for an integer m in [1, 10^18]. Return the number of positive integers x <= m whose decimal representation has no zero, uses every digit at most once, and has no internal valley a > b < c. The string boundary preserves exact 64-bit limits in every supported language.
Constraints
- m_decimal is the canonical decimal representation of 1 <= m <= 10^18.
- Good numbers use only digits 1 through 9 and never repeat a digit.
- For every three consecutive digits a, b, c, the pattern a > b < c is forbidden.
- A good number has at most nine digits.
Examples
Input: ("1",)
Expected Output: 1
Explanation: Only the number one is included.
Input: ("5",)
Expected Output: 5
Explanation: Every positive one-digit number up to five is good.
Hints
- Use digit DP with tight and started flags plus a used-digit bitmask.
- Keep the previous two chosen digits so appending a digit can detect a newly completed valley.
- Leading padding zeroes are not part of the number and must not enter the mask.
Community answers
Answer by Josef420
The input examples are pretty bad