# Find the K-Beauty of a Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-k-beauty-of-a-number)
Canonical: https://scaleengineer.com/dsa/problems/find-the-k-beauty-of-a-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [Quora](https://scaleengineer.com/companies/quora), [Postmates](https://scaleengineer.com/companies/postmates)
---
## 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 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 "**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:**

**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 <= 109`
* `1 <= k <= num.length` (taking `num` as a string)

# Approaches
## Naive String Substring Iteration
This is the most straightforward approach. It converts the number to a string and then iterates through all possible starting positions to extract substrings of length `k`. Each substring is then converted back to an integer to check for the divisibility condition.
**Time:** O(D * k), where `D` is the number of digits in `num`. The loop runs `D - k + 1` times. In each iteration, `substring()` takes `O(k)` time (in modern Java versions) and `Integer.parseInt()` also takes `O(k)` time. This results in a total complexity of `O((D-k) * k)`, which simplifies to `O(D * k)`. · **Space:** O(D). This is required to store the string representation of `num`, where `D` is the number of digits. Additionally, each call to `substring()` creates a new string of length `k`, contributing `O(k)` temporary space within the loop.
**Pros:** Very simple and intuitive to write and understand.; Directly translates the problem statement into code.
**Cons:** Less efficient due to repeated creation and parsing of substrings. For each step of the iteration, it re-parses `k-1` digits that were already part of the previous substring.
### Explanation
The algorithm works by first converting the number `num` into a string `s` to easily access its digits. It then iterates from the beginning of the string to the last possible starting point for a substring of length `k`. In each iteration, it extracts the `k`-length substring, converts it to an integer, and checks if this integer is a non-zero divisor of the original number `num`. A counter is maintained to keep track of how many such substrings are found, which is the final k-beauty value.

```java
class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = Integer.toString(num);
        int n = s.length();
        int count = 0;
        
        if (k > n) {
            return 0;
        }
        
        for (int i = 0; i <= n - k; i++) {
            // Extract substring of length k
            String subStr = s.substring(i, i + k);
            
            // Convert substring to integer
            int subNum = Integer.parseInt(subStr);
            
            // Check for k-beauty conditions
            if (subNum != 0 && num % subNum == 0) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Convert the input integer `num` to its string representation, `s`.
- Initialize a counter, `kBeautyCount`, to zero.
- Loop through the string `s` from the first character up to the character at index `s.length() - k`. Let the loop variable be `i`.
- Inside the loop, extract the substring of length `k` starting at index `i` using `s.substring(i, i + k)`.
- Convert this substring into an integer, let's call it `subNumber`.
- Check if `subNumber` is not zero.
- If `subNumber` is not zero, perform a modulo operation: `num % subNumber`. If the result is 0, it means `subNumber` is a divisor of `num`.
- If `subNumber` is a non-zero divisor, increment `kBeautyCount`.
- After the loop finishes, return `kBeautyCount`.

## Optimized Sliding Window on String
This approach improves upon the naive method by avoiding repeated parsing of overlapping parts of the number. It first parses the initial `k`-digit number. Then, it "slides" a window of `k` digits across the string representation of the number one position at a time, updating the integer value of the window using simple arithmetic instead of re-parsing the entire substring.
**Time:** O(D), where `D` is the number of digits in `num`. Converting the number to a string takes `O(D)`. The initial window setup takes `O(k)`. The main loop runs `D - k` times, and each iteration involves constant-time arithmetic operations. The total time is `O(D) + O(k) + O(D - k)`, which simplifies to `O(D)`. · **Space:** O(D). The space is dominated by the storage required for the string representation of `num`, where `D` is the number of digits.
**Pros:** More efficient than the naive approach, with a linear time complexity relative to the number of digits.; Avoids expensive repeated substring creation and parsing operations inside the main loop.
**Cons:** The implementation is slightly more complex than the naive approach.; Still requires converting the number to a string, which uses extra space.
### Explanation
This optimized method still begins by converting the number to a string. However, instead of repeatedly calling `substring` and `parseInt`, it calculates the integer value of the first `k`-digit window once. Then, it iterates through the rest of the string, and for each step, it updates the window's integer value in constant time. This is done by arithmetically removing the value of the digit that's leaving the window and adding the value of the new digit that's entering. This avoids the `O(k)` cost of re-parsing at each step, leading to a more efficient overall solution.

```java
class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = Integer.toString(num);
        int n = s.length();
        int count = 0;

        if (k > n) {
            return 0;
        }

        long windowValue = 0;
        long powerOf10 = 1;

        // Calculate initial window value and the power of 10 needed for sliding
        for (int i = 0; i < k; i++) {
            windowValue = windowValue * 10 + (s.charAt(i) - '0');
            if (i < k - 1) {
                powerOf10 *= 10;
            }
        }

        // Check the first window
        if (windowValue != 0 && num % windowValue == 0) {
            count++;
        }

        // Slide the window across the rest of the string
        for (int i = k; i < n; i++) {
            // Update window value: remove leading digit's effect, shift, add new digit
            windowValue = (windowValue % powerOf10) * 10 + (s.charAt(i) - '0');
            
            // Check for k-beauty conditions
            if (windowValue != 0 && num % windowValue == 0) {
                count++;
            }
        }

        return count;
    }
}
```
### Algorithm
- Convert the input integer `num` to its string representation, `s`.
- Initialize a counter, `kBeautyCount`, to zero.
- Calculate the value of the first `k`-digit substring and store it in `windowValue`.
- Check if this initial `windowValue` meets the k-beauty conditions and update the count if it does.
- Pre-calculate `powerOf10 = 10^(k-1)`. This will be used to efficiently update the window's value.
- Loop from `i = k` to `s.length() - 1`. This loop slides the window to the right.
- In each iteration, update `windowValue` arithmetically to reflect the new window:
  - Use the modulo operator to remove the most significant digit: `windowValue = windowValue % powerOf10`.
  - Shift the remaining digits to the left: `windowValue = windowValue * 10`.
  - Add the value of the new rightmost digit: `windowValue = windowValue + (s.charAt(i) - '0')`.
- Check if the updated `windowValue` meets the k-beauty conditions and increment the count accordingly.
- After the loop, return `kBeautyCount`.

# Solutions
### Java

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

```

### Python

```python
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

```

### CPP

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

```