Find the K-Beauty of a Number

Difficulty: Easy | Acceptance: 63.30% | Paid: No Topics: Math, String, Sliding Window

The k-beauty of an integer num is defined as the number of substrings of num (when represented as a string) that are of length k and are divisors of num.

Note that leading zeros are allowed. For example, 002 is a valid substring of 2002, but 2 is not.

Return the k-beauty of num.

• Examples
• Constraints
• String Iteration
• Mathematical Sliding Window

Examples

Example 1:

Input: num = 240, k = 2
Output: 2
Explanation: The substrings of length 2 in "240" are:
"24": 24 is a divisor of 240.
"40": 40 is a divisor of 240.

Example 2:

Input: num = 430043, k = 2
Output: 2
Explanation: The substrings of length 2 in "430043" are:
"43": 43 is a divisor of 430043.
"30": 30 is not a divisor of 430043.
"00": 0 is not a divisor of 430043.
"04": 4 is not a divisor of 430043.
"43": 43 is a divisor of 430043.

Constraints

1 <= num <= 10⁹
1 <= k <= num.length

String Iteration

Intuition Convert the integer to a string to easily access and slice substrings of length k. Iterate through the string, convert each substring back to an integer, and check if it divides the original number.

Steps

• Convert num to a string s.
• Initialize count to 0.
• Iterate i from 0 to len(s) - k.
• Extract the substring s[i : i + k].
• Convert the substring to an integer val.
• If val is not 0 and num % val == 0, increment count.
• Return count.

Complexity

• Time: O(n * k) where n is the number of digits. Converting substring to int takes O(k) time.
• Space: O(n) to store the string representation of the number.
• Notes: Simple and readable, but involves string allocation.

Mathematical Sliding Window

Intuition Avoid string conversion by using mathematical operations to extract digits. We can calculate the first window of k digits, then slide it across the number by removing the most significant digit and adding the next least significant digit.

Steps

• Determine the number of digits n in num.
• Calculate divisor = 10^(n-k) to isolate the first k digits.
• Extract the first window = num / divisor.
• Check if window is a valid divisor.
• Loop n - k times to slide the window:
  • Remove the leading digit: window = window % 10^(k-1).
  • Update divisor to access the next digit.
  • Extract the next_digit from num.
  • Update window = window * 10 + next_digit.
  • Check if the new window is a valid divisor.

Complexity

• Time: O(n) where n is the number of digits. We process each digit a constant number of times.
• Space: O(1) extra space, excluding the space for the input.
• Notes: More complex to implement but avoids string allocation overhead.