Count Perfect Wake Numbers: Distinct Nonzero Digits, Inner Digits as Peaks
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A positive integer is a **perfect wake number** when its decimal digits satisfy three conditions: it contains no `0`, no digit repeats, and the two digits next to a digit are never higher than that digit. The interview first asked for a function that decides whether one number is a perfect wake number (for example, `123` is not), then asked how many perfect wake numbers lie between `1` and `9999`. Write one function that covers both: count the perfect wake numbers in the inclusive range `[low, high]`, where `high` is at most `9999`. When `low == high`, the result is `1` if that number is a perfect wake number and `0` otherwise.
The report states the third condition loosely. Applied to the first and last digits as well, it would rule out every number with two or more digits, because of two adjacent different digits one is always higher than the other. This version therefore assumes it applies only to digits that have a neighbor on both sides, as the Rules state. Under that reading no four-digit number is a perfect wake number: its second and third digits each have a neighbor on both sides and sit next to each other, so each would have to be greater than the other. Every perfect wake number in the range has one, two or three digits.
### Function Signature
```python
def count_perfect_wake_numbers(low: int, high: int) -> int:
```
### Rules
- Write `n` in decimal without leading zeros. `n` is a perfect wake number when all three conditions hold:
1. No digit of `n` is `0`.
2. No digit appears more than once in `n`.
3. Every digit that has a neighbor on both sides is greater than both of those neighbors. Because the digits are distinct, "not higher than" is the same as "lower than". The first and last digits have only one neighbor each and are not checked by this condition.
- Every one-digit number from `1` to `9` is a perfect wake number, and so is every two-digit number whose two digits are different and nonzero.
- No four-digit number is a perfect wake number, for the reason given above.
- Return the number of perfect wake numbers `n` with `low <= n <= high`.
### Constraints
- `1 <= low <= high <= 9999`
- The result is an integer from `0` to `high - low + 1`.
### Examples
**Example 1**
```text
Input: low = 123, high = 123
Output: 0
```
`123` has no zero and no repeated digit, but its middle digit `2` has the neighbor `3`, which is higher, so `123` is not a perfect wake number. This is the example given in the interview.
**Example 2**
```text
Input: low = 100, high = 200
Output: 28
```
`200` and every number from `100` to `109` contain a `0`. The numbers that qualify all have the form `1`, then a middle digit greater than both outer digits, then a last digit other than `0` and `1`: `132`, `142`, `143`, and so on up to `198`. There are 28 of them.
**Example 3**
```text
Input: low = 1, high = 9999
Output: 249
```
This is the count asked for in the interview's follow-up. It is made up of the nine one-digit numbers, the 72 two-digit numbers with two different nonzero digits, and 168 three-digit numbers. No four-digit number contributes.
Overview: A coding problem about perfect wake numbers: positive integers with no zero digit, no repeated digit, and every inner digit greater than both of its neighbors. Implement a function that counts these numbers in an inclusive range up to 9999, which doubles as a single-number check, testing digit handling and precise reading of an adjacency rule.
Read the full Google Software Engineer interview experience this question came from
A positive integer `n` is a **perfect wake number** when its decimal digits, written without leading zeros, satisfy all three conditions:
1. No digit of `n` is `0`.
2. No digit appears more than once in `n`.
3. Every digit that has a neighbor on both sides is greater than both of those neighbors. The first and last digits have only one neighbor each and are not checked by this condition.
Because the digits are distinct, a neighbor that is not higher than a digit is lower than it. Every one-digit number from `1` to `9` is a perfect wake number, and so is every two-digit number whose two digits are different and nonzero. No four-digit number is a perfect wake number: its second and third digits each have a neighbor on both sides and sit next to each other, so each would have to be greater than the other. Every perfect wake number in the allowed range therefore has one, two or three digits.
Given two integers `low` and `high`, return how many perfect wake numbers `n` satisfy `low <= n <= high` (both endpoints are inclusive). When `low == high`, the result is `1` if that number is a perfect wake number and `0` otherwise.
Implement `count_perfect_wake_numbers(low, high)`, which returns this count as an integer.
### Constraints
- `1 <= low <= high <= 9999`
- The result is an integer from `0` to `high - low + 1`.
- No input or result exceeds 2^31 - 1, so a 32-bit `int` suffices in every language.
### Example 1
```text
Input: low = 123, high = 123
Output: 0
```
`123` has no zero and no repeated digit, but its middle digit `2` has the neighbor `3`, which is higher, so `123` is not a perfect wake number.
### Example 2
```text
Input: low = 100, high = 200
Output: 28
```
`200` and every number from `100` to `109` contain a `0`. The numbers that qualify all have the form `1`, then a middle digit greater than both outer digits, then a last digit other than `0` and `1`: `132`, `142`, `143`, and so on up to `198`. There are 28 of them.
Constraints
- 1 <= low <= high <= 9999
- The result is an integer from 0 to high - low + 1.
- No input or result exceeds 2^31 - 1, so a 32-bit int suffices in every language.
Examples
Input: (1, 1)
Expected Output: 1
Explanation: Minimum valid input: the one-digit number 1 is a perfect wake number.
Input: (123, 123)
Expected Output: 0
Explanation: Source example: the middle digit 2 is lower than its neighbor 3.
Hints
- The interview first asked whether a single number is a perfect wake number; start with a check for one number against the three conditions.
- Condition 3 constrains only digits that have a neighbor on both sides, so the first and last digits are limited only by conditions 1 and 2.
- Consider how many digits a perfect wake number can have: what would two interior digits that sit next to each other each need to satisfy?