Skip to content

2269. Find the K-Beauty of a Number

Description

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 of num.

Note:

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

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

 

Example 1:

Input: num = 240, k = 2
Output: 2
Explanation: 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
Explanation: 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)

Solutions

Solution 1: Enumeration

Thinking

The \(k\)-beauty counts length-\(k\) substrings that divide the number. \(num \le 10^9\) has few digits, so converting every window of length \(k\) is enough; skip a zero divisor.

Stringify \(num\) and take \(s[i:i+k]\) at each start.

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.

The time complexity is \(O(\log num \times k)\), and the space complexity is \(O(\log num + k)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int divisorSubstrings(int num, int k) {
        int ans = 0;
        String s = "" + num;
        for (int i = 0; i < s.length() - k + 1; ++i) {
            int t = Integer.parseInt(s.substring(i, i + k));
            if (t != 0 && num % t == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        int ans = 0;
        string s = to_string(num);
        for (int i = 0; i < s.size() - k + 1; ++i) {
            int t = stoi(s.substr(i, k));
            ans += t && num % t == 0;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func divisorSubstrings(num int, k int) int {
    ans := 0
    s := strconv.Itoa(num)
    for i := 0; i < len(s)-k+1; i++ {
        t, _ := strconv.Atoi(s[i : i+k])
        if t > 0 && num%t == 0 {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function divisorSubstrings(num: number, k: number): number {
    let ans = 0;
    const s = num.toString();
    for (let i = 0; i < s.length - k + 1; ++i) {
        const t = parseInt(s.substring(i, i + k));
        if (t !== 0 && num % t === 0) {
            ++ans;
        }
    }
    return ans;
}

Solution 2: Sliding Window

Thinking

Solution 1 rebuilds an integer from a slice each time. A decimal window can drop the low digit and insert a new high digit in \(O(1)\).

Extract the lowest \(k\) digits as \(x\), then repeatedly divide \(x\) by \(10\) and add the next digit at the top, testing divisibility as we go.

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.

The time complexity is \(O(\log num)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        x, p = 0, 1
        t = num
        for _ in range(k):
            t, v = divmod(t, 10)
            x = p * v + x
            p *= 10
        ans = int(x != 0 and num % x == 0)
        p //= 10
        while t:
            x //= 10
            t, v = divmod(t, 10)
            x = p * v + x
            ans += int(x != 0 and num % x == 0)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int divisorSubstrings(int num, int k) {
        int x = 0, p = 1;
        int t = num;
        for (; k > 0; --k) {
            int v = t % 10;
            t /= 10;
            x = p * v + x;
            p *= 10;
        }
        int ans = x != 0 && num % x == 0 ? 1 : 0;
        for (p /= 10; t > 0; t /= 10) {
            x /= 10;
            int v = t % 10;
            x = p * v + x;
            ans += (x != 0 && num % x == 0 ? 1 : 0);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int divisorSubstrings(int num, int k) {
        int x = 0;
        long long p = 1;
        int t = num;
        for (; k > 0; --k) {
            int v = t % 10;
            t /= 10;
            x = p * v + x;
            p *= 10;
        }
        int ans = x != 0 && num % x == 0 ? 1 : 0;
        for (p /= 10; t > 0; t /= 10) {
            x /= 10;
            int v = t % 10;
            x = p * v + x;
            ans += (x != 0 && num % x == 0 ? 1 : 0);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func divisorSubstrings(num int, k int) (ans int) {
    x, p, t := 0, 1, num
    for ; k > 0; k-- {
        v := t % 10
        t /= 10
        x = p*v + x
        p *= 10
    }
    if x != 0 && num%x == 0 {
        ans++
    }
    for p /= 10; t > 0; t /= 10 {
        x /= 10
        v := t % 10
        x = p*v + x
        if x != 0 && num%x == 0 {
            ans++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function divisorSubstrings(num: number, k: number): number {
    let [x, p, t] = [0, 1, num];
    for (; k > 0; k--) {
        const v = t % 10;
        t = Math.floor(t / 10);
        x = p * v + x;
        p *= 10;
    }
    let ans = x !== 0 && num % x === 0 ? 1 : 0;
    for (p = Math.floor(p / 10); t > 0; t = Math.floor(t / 10)) {
        x = Math.floor(x / 10);
        x = p * (t % 10) + x;
        ans += x !== 0 && num % x === 0 ? 1 : 0;
    }
    return ans;
}

Comments