#2269

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Find the K-Beauty of a Number

Calculate the k-beauty of a number by counting substrings of length k that divide the original number evenly using a sliding window.

math string sliding window

Problem Statement

Given an integer num and another integer k, define the k-beauty of num as the number of substrings of length k in num that evenly divide num when interpreted as integers. A substring starting with 0 is considered valid but cannot divide the number.

Return the total count of these substrings. Constraints include 1 <= num <= 10^9 and 1 <= k <= length of num when num is treated as a string. Substrings should be evaluated in their original order for divisibility.

Examples

Example 1

Input: num = 240, k = 2

Output: 2

The following are the substrings of num of length k:

"24" from "240": 24 is a divisor of 240.
"40" from "240": 40 is a divisor of 240. Therefore, the k-beauty is 2.

Example 2

Input: num = 430043, k = 2

Output: 2

The following are the substrings of num of length k:

"43" from "430043": 43 is a divisor of 430043.
"30" from "430043": 30 is not a divisor of 430043.
"00" from "430043": 0 is not a divisor of 430043.
"04" from "430043": 4 is not a divisor of 430043.
"43" from "430043": 43 is a divisor of 430043. Therefore, the k-beauty is 2.

Constraints

1 <= num <= 109
1 <= k <= num.length (taking num as a string)

Solution Approach

Convert Number to String and Slide

Treat the integer num as a string to easily access all substrings of length k. Use a sliding window of size k to iterate over each substring efficiently.

Check Divisibility for Each Substring

Convert each substring to an integer and skip if it is zero. If the integer divides num evenly, increment the k-beauty count. This captures the exact definition of k-beauty.

Return the Total Count

After scanning all substrings, return the total count as the k-beauty. This leverages the sliding window pattern to avoid repeated string slicing overhead.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the number of digits in num, because each substring of length k is checked once. Space complexity is O(1) beyond the input string conversion, as only a counter and temporary substring integer are used.

What Interviewers Usually Probe

Expect candidates to recognize the sliding window pattern for substring evaluation.
Check if candidates handle zero substrings correctly to avoid division errors.
Listen for explanations about optimizing substring checks versus naive repeated slicing.

Common Pitfalls or Variants

Common pitfalls

Ignoring substrings that start with 0 and assuming they divide num.
Converting substrings inefficiently in a loop without sliding window optimization.
Miscounting the total when the substring integer does not divide evenly.

Follow-up variants

Compute k-beauty for a list of numbers rather than a single num.
Return all valid substrings that contribute to k-beauty instead of just the count.
Allow k to vary dynamically for multiple queries on the same number.

FAQ

What is the k-beauty of a number?

It is the count of substrings of length k from num that evenly divide the number when interpreted as integers.

Can substrings starting with 0 be counted?

Yes, they are considered as substrings, but they cannot divide num evenly.

What pattern does this problem use?

It uses a sliding window pattern to extract substrings efficiently while updating the running state.

How do I handle large numbers efficiently?

Convert num to a string once and use the sliding window approach rather than repeatedly slicing or converting.

Does GhostInterview provide solutions for the k-beauty calculation?

Yes, it evaluates each substring, handles edge cases, and counts the k-beauty automatically.

terminal

Solution

Solution 1: Enumeration

We can convert $num$ to a string $s$, then enumerate all substrings of $s$ with length $k$, convert them to an integer $t$, and check if $t$ is divisible by $num$. If it is, we increment the answer.

1

2

3

4

5

6

7

8

9

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        ans = 0
        s = str(num)
        for i in range(len(s) - k + 1):
            t = int(s[i : i + k])
            if t and num % t == 0:
                ans += 1
        return ans

Solution 2: Sliding Window

We can maintain a sliding window of length $k$. Initially, the window contains the lowest $k$ digits of $num$. Then, for each iteration, we move the window one digit to the right, update the number in the window, and check if the number in the window is divisible by $num$. If it is, we increment the answer.

1

2

3

4

5

6

7

8

9

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        ans = 0
        s = str(num)
        for i in range(len(s) - k + 1):
            t = int(s[i : i + k])
            if t and num % t == 0:
                ans += 1
        return ans

Continue Practicing

#2266 count number of texts #2379 minimum recolors to get k consecutive black blocks #2156 find substring with given hash value