Scale Engineer

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
MathSliding Window
Data structures
String
Companies
QuoraPostmates

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 <= 109
  • 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.

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

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.

Solutions

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

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 →

Next problem