277. Self-Dividing Range
A puzzle magazine calls a positive integer generous if it contains no digit 0 and is evenly divisible by every one of its own decimal digits. The number 128 is generous because it is divisible by 1, 2 and 8, while 102 is not (it has a zero digit) and 26 is not (it is not divisible by 6).
Given the two integers left and right, return an array of all generous numbers in the inclusive range [left, right] in ascending order. If there are none, return an empty array. The range is at most ten thousand numbers wide, so testing every number by extracting its digits is intended; do not build strings if you can avoid it.
Example 1
- Input:
- left = 95, right = 130
- Output:
- [99,111,112,115,122,124,126,128]
- Explanation:
Within 95..130 the generous numbers are 99, 111, 112, 115, 122, 124, 126 and 128.
Example 2
- Input:
- left = 300, right = 330
- Output:
- [312,315,324]
- Explanation:
Only 312, 315 and 324 divide evenly by each of their digits in this window.
Example 3
- Input:
- left = 20, right = 20
- Output:
- []
- Explanation:
20 contains a zero digit, so the result is empty.
Constraints
1 ≤ left ≤ right ≤ 231 - 1
right - left ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O((right - left) * log10(right))
- Space
- O(1) beyond the output