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

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)\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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

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)\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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