Problem Description

Given an integer num and an integer k, the K-Beauty of num is defined as the number of substrings of length k in the decimal representation of num that are non-zero and divide num evenly (i.e., num % substring == 0).

Return the K-Beauty of num. Each substring must be a contiguous sequence of digits of length k in num, and substrings with leading zeros are valid as long as their integer value is not zero.

• Each substring is considered separately, even if values repeat.
• Substrings with value zero are ignored (cannot divide num).
• num is a positive integer, and k is a positive integer less than or equal to the number of digits in num.

Thought Process

The problem asks us to count how many substrings of length k in the number num are non-zero and divide num evenly. The brute-force way is to extract all possible substrings of length k from the number, convert each to an integer, check if it's non-zero, and then check if it divides num with no remainder.

Initially, it's tempting to treat num as a number, but since we need substrings, it's easier to convert it to a string. This allows for simple substring extraction. For each substring, we must handle leading zeros and avoid division by zero.

Optimization isn't critical here, as the number of substrings is at most the number of digits in num. However, we can make the code concise and efficient by looping just once through the string and checking each substring.

Solution Approach

• Step 1: Convert num to its string representation so we can easily extract substrings.
• Step 2: Loop through the string, extracting every possible substring of length k.
• Step 3: For each substring:
  • Convert it to an integer.
  • If the integer is zero, skip it (to avoid division by zero).
  • Otherwise, check if num is divisible by this integer (i.e., num % value == 0).
  • If so, increment a counter.
• Step 4: Return the final count after processing all substrings.

This approach is efficient because it processes each substring exactly once and uses basic arithmetic operations.

Example Walkthrough

Consider num = 240 and k = 2. The string representation is "240".

• First substring: "24" (from index 0 to 1). Integer value is 24. 240 % 24 == 0, so count = 1.
• Second substring: "40" (from index 1 to 2). Integer value is 40. 240 % 40 == 0, so count = 2.

There are no more substrings of length 2. So, the K-Beauty of 240 with k=2 is 2.

Time and Space Complexity

• Brute-force approach: Extract all substrings of length k and check each one. For a number with n digits, we process n - k + 1 substrings. Each check is O(1). So, total time complexity is O(n).
• Space complexity: We only need a few variables for counting and substring extraction, so space is O(1) (ignoring the string conversion, which is at most O(n)).
• Optimized approach: Since the brute-force is already O(n), further optimization is unnecessary.

Summary

To solve the K-Beauty of a Number problem, we convert the number to a string, extract all substrings of length k, and count those that are non-zero and divide the original number evenly. The approach is straightforward, efficient, and leverages basic string and arithmetic operations. The main insight is to treat the number as a string to simplify substring handling, ensuring we avoid division by zero and count only valid divisors.

Code Implementation

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

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);
        int count = 0;
        for (int i = 0; i <= s.size() - k; ++i) {
            int sub = stoi(s.substr(i, k));
            if (sub != 0 && num % sub == 0) {
                count++;
            }
        }
        return count;
    }
};
      

class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = Integer.toString(num);
        int count = 0;
        for (int i = 0; i <= s.length() - k; i++) {
            int sub = Integer.parseInt(s.substring(i, i + k));
            if (sub != 0 && num % sub == 0) {
                count++;
            }
        }
        return count;
    }
}
      

var divisorSubstrings = function(num, k) {
    const s = num.toString();
    let count = 0;
    for (let i = 0; i <= s.length - k; i++) {
        let sub = parseInt(s.substring(i, i + k));
        if (sub !== 0 && num % sub === 0) {
            count++;
        }
    }
    return count;
};