Problem

The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:

  • It has a length of k.
  • It is a divisor of num.

Given integers num and k, return the k-beauty ofnum.

Note:

  • Leading zeros are allowed.
  • 0 is not a divisor of any value.

A substring is a contiguous sequence of characters in a string.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    
    
    Input: num = 240, k = 2
    Output: 2
    Explanation: The following are the substrings of num of length k:
    - "24" from "**_24_** 0": 24 is a divisor of 240.
    - "40" from "2 _**40**_ ": 40 is a divisor of 240.
    Therefore, the k-beauty is 2.
    

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    
    
    Input: num = 430043, k = 2
    Output: 2
    Explanation: The following are the substrings of num of length k:
    - "43" from "_**43**_ 0043": 43 is a divisor of 430043.
    - "30" from "4 _**30**_ 043": 30 is not a divisor of 430043.
    - "00" from "43 _**00**_ 43": 0 is not a divisor of 430043.
    - "04" from "430 _**04**_ 3": 4 is not a divisor of 430043.
    - "43" from "4300 _**43**_ ": 43 is a divisor of 430043.
    Therefore, the k-beauty is 2.
    

Constraints

  • 1 <= num <= 10^9
  • 1 <= k <= num.length (taking num as a string)

Solution

Method 1 – Sliding Window Substring Check

Intuition

We want to count how many substrings of length k in the string representation of num are divisors of num. We can use a sliding window to extract each substring, convert it to an integer, and check if it divides num (ignoring zero substrings).

Approach

  1. Convert num to a string s.
  2. For each index i from 0 to len(s) - k:
    • Extract the substring s[i:i+k].
    • Convert it to an integer val.
    • If val is not zero and num % val == 0, increment the answer.
  3. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);
        int ans = 0;
        for (int i = 0; i <= s.size() - k; ++i) {
            int val = stoi(s.substr(i, k));
            if (val != 0 && num % val == 0) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func divisorSubstrings(num int, k int) int {
    s := strconv.Itoa(num)
    ans := 0
    for i := 0; i <= len(s)-k; i++ {
        val, _ := strconv.Atoi(s[i:i+k])
        if val != 0 && num%val == 0 {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = Integer.toString(num);
        int ans = 0;
        for (int i = 0; i <= s.length() - k; ++i) {
            int val = Integer.parseInt(s.substring(i, i + k));
            if (val != 0 && num % val == 0) ++ans;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    fun divisorSubstrings(num: Int, k: Int): Int {
        val s = num.toString()
        var ans = 0
        for (i in 0..s.length - k) {
            val valNum = s.substring(i, i + k).toInt()
            if (valNum != 0 && num % valNum == 0) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)
        ans = 0
        for i in range(len(s) - k + 1):
            val = int(s[i:i+k])
            if val != 0 and num % val == 0:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn divisor_substrings(num: i32, k: i32) -> i32 {
        let s = num.to_string();
        let mut ans = 0;
        let k = k as usize;
        for i in 0..=s.len()-k {
            let val = s[i..i+k].parse::<i32>().unwrap();
            if val != 0 && num % val == 0 {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    divisorSubstrings(num: number, k: number): number {
        const s = num.toString();
        let ans = 0;
        for (let i = 0; i <= s.length - k; ++i) {
            const val = parseInt(s.substring(i, i + k));
            if (val !== 0 && num % val === 0) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of digits in num, since we check each substring of length k once.
  • 🧺 Space complexity: O(1), as we use only a constant amount of extra space.