Watch 10 video solutions for Find the K-Beauty of a Number, a easy level problem involving Math, String, Sliding Window. This walkthrough by Programming Live with Larry has 2,404 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
k.num.Given integers num and k, return the k-beauty of num.
Note:
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)Problem Overview: You are given an integer num and an integer k. The k-beauty of the number is the count of substrings of length k that, when converted to integers, divide num without remainder. Substrings with value 0 are ignored because division by zero is undefined.
Approach 1: Direct Substring Calculation and Check (O(n * k) time, O(1) space)
Convert the number to a string and iterate through every substring of length k. For each index i, extract s[i:i+k], convert it to an integer, and check two conditions: the value is not zero and num % value == 0. Increment a counter whenever both conditions hold. The conversion from substring to integer costs O(k), so with roughly n substrings the total time becomes O(n * k). Space usage remains O(1) because only a few variables are maintained. This approach is simple and easy to implement, making it a good baseline.
Approach 2: Sliding Window Approach (O(n) time, O(1) space)
The direct approach repeatedly converts substrings to integers, which is unnecessary work. A more efficient strategy uses a sliding window of length k that maintains the current substring value as a number. Start by building the integer value for the first k digits. Then slide the window one digit at a time: remove the leftmost digit contribution and append the new rightmost digit. This update takes constant time using basic math operations. At each step, check if the current window value is non‑zero and divides num. Because each digit enters and leaves the window exactly once, the total runtime becomes O(n). Only a few integers are stored, so space complexity stays O(1).
Recommended for interviews: The sliding window approach is what interviewers typically expect. It demonstrates that you recognize repeated work in substring parsing and optimize it by maintaining the numeric value incrementally. The direct substring approach is still useful to explain first because it clearly models the problem and shows you understand the constraints before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Substring Calculation and Check | O(n * k) | O(1) | Best for quick implementation or when constraints are small and clarity matters more than optimization. |
| Sliding Window | O(n) | O(1) | Preferred for large inputs or interviews since it avoids repeated substring parsing. |