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.
The Sliding Window approach can be used to efficiently extract all possible substrings of length k and check if they divide the number num. The key idea is to maintain a window of size k and slide it over the number represented as a string.
This code first converts the integer num into a string format. It then loops through each possible starting index of a substring of length k in this string representation, extracting the substring, converting it back to an integer, and checking if it divides num. If it does, the count is incremented.
Time complexity: O(n*k), where n is the length of the number when represented as a string.
Space complexity: O(k) for the substring storage.
This approach directly calculates and iterates over each possible substring of length k and checks its divisibility by converting it to an integer. It uses a straightforward iteration process without additional string building steps.
This C implementation iteratively constructs substrings as numeric values using a nested loop to avoid re-allocating new strings, directly checking divisibility.
Time complexity: O(n*k).
Space complexity: O(1), as it uses linear space.
We can convert num to a string s, then enumerate all substrings of s with length k, convert them to an integer t, and check if t is divisible by num. If it is, we increment the answer.
The time complexity is O(log num times k), and the space complexity is O(log num + k).
Python
Java
C++
Go
TypeScript
We can maintain a sliding window of length k. Initially, the window contains the lowest k digits of num. Then, for each iteration, we move the window one digit to the right, update the number in the window, and check if the number in the window is divisible by num. If it is, we increment the answer.
The time complexity is O(log num), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time complexity: O(n*k), where n is the length of the number when represented as a string. |
| Direct Substring Calculation and Check | Time complexity: O(n*k). |
| Enumeration | — |
| Sliding Window | — |
| 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. |
2269. Find the K-Beauty of a Number (Leetcode Easy) • Programming Live with Larry • 2,404 views views
Watch 9 more video solutions →Practice Find the K-Beauty of a Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor