Find the K-Beauty of a Number

EASY

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

Approaches

Checkout 2 different approaches to solve Find the K-Beauty of a Number. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the K-Beauty of a Number. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find the K-Beauty of a Number

Patterns:

MathSliding Window

Data Structures:

String

Companies:

Quora |Postmates |