1. Find the K-Beauty of a Number (LeetCode)
Model answer
The task
Count the length-k digit sequences in num whose numeric value is a nonzero divisor of num. Sequences with leading zeroes are still considered windows.
Key idea
Scan the digits with a sliding numeric window, updating its value in constant time per digit. Check divisibility only when the window is nonzero.
Approach
- Convert
numto a string so windows retain their original digits. - Return
0ifkis longer than the digit string. - Build the first window’s numeric value.
- For each window, count it if it is nonzero and divides
num. - Slide forward by removing the leading digit and appending the next digit.
class Solution:
def divisorSubstrings(self, num: int, k: int) -> int:
digits = str(num)
if k > len(digits):
return 0
# Keep the last k - 1 digits when shifting the window.
base = 10 ** (k - 1)
window = int(digits[:k])
count = 0
for start in range(len(digits) - k + 1):
if window != 0 and num % window == 0:
count += 1
# Advance to the next length-k window.
if start + k < len(digits):
window = (window % base) * 10 + int(digits[start + k])
return count
Complexity:
- Time: O(d), where
dis the number of digits, assuming arithmetic on these values takes constant time. - Space: O(d) for the digit string.
Common follow-ups
- What if
kexceeds the number of digits? Return0; no window of that length exists. - Why skip zero-valued windows? Division by zero is undefined, so they cannot be divisors.
- How would you handle a number too large for built-in integer types? Keep the original number as a digit string and use an appropriate big-integer or modular arithmetic strategy for divisibility checks.