Easy

Find the K-Beauty of a Number

LAB

Return how many length-k digit substrings of num are nonzero divisors of num.

EXAMPLES

Example 1

Input
{
  "num": 240,
  "k": 2
}

Output
2

FUNCTION SHAPE

num: intk: int→int

SOLUTION NOTE

Window = int(s[i-(k-1):i+1]). Valid: window != 0 and num % window == 0.

Reveal reference solution +

pythonREFERENCE

# Simple approach
def divisorSubstrings(self, num: int, k: int) -> int:
    s = str(num)
    n = len(s)
    res = 0

    for i in range(n):
        if i >= k - 1:
            window = int(s[i-(k-1):i+1])
            if window != 0 and num % window == 0:
                res += 1

    return res

# Optimized - compute window on the fly
def divisorSubstrings(self, num: int, k: int) -> int:
    s = str(num)
    n = len(s)
    res = 0
    window = 0
    pow_ = 10 ** (k - 1)

    for i in range(n):
        window = 10 * window + int(s[i])
        if i >= k - 1:
            if window != 0 and num % window == 0:
                res += 1
            window %= pow_

    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗