Find the K-Beauty of a Number

Easy

#2067Time: 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.2 companies

Patterns

Math Sliding Window

Data structures

String

Companies

Quora Postmates

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int divisorSubstrings(int num, int k) {3        String s = Integer.toString(num);4        int n = s.length();5        int count = 0;6        7        if (k > n) {8            return 0;9        }10        11        for (int i = 0; i <= n - k; i++) {12            // Extract substring of length k13            String subStr = s.substring(i, i + k);14            15            // Convert substring to integer16            int subNum = Integer.parseInt(subStr);17            18            // Check for k-beauty conditions19            if (subNum != 0 && num % subNum == 0) {20                count++;21            }22        }23        24        return count;25    }26}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int divisorSubstrings(int num, int k) {3        String s = Integer.toString(num);4        int n = s.length();5        int count = 0;6 7        if (k > n) {8            return 0;9        }10 11        long windowValue = 0;12        long powerOf10 = 1;13 14        // Calculate initial window value and the power of 10 needed for sliding15        for (int i = 0; i < k; i++) {16            windowValue = windowValue * 10 + (s.charAt(i) - '0');17            if (i < k - 1) {18                powerOf10 *= 10;19            }20        }21 22        // Check the first window23        if (windowValue != 0 && num % windowValue == 0) {24            count++;25        }26 27        // Slide the window across the rest of the string28        for (int i = k; i < n; i++) {29            // Update window value: remove leading digit's effect, shift, add new digit30            windowValue = (windowValue % powerOf10) * 10 + (s.charAt(i) - '0');31            32            // Check for k-beauty conditions33            if (windowValue != 0 && num % windowValue == 0) {34                count++;35            }36        }37 38        return count;39    }40}

Complexity

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.

Trade-offs

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.

Solutions

Solution

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

1class Solution:2    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

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem