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 <= 1091 <= 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 × k), and the space complexity is O(log num + k).
PythonJavaC++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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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).
PythonJavaC++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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
