Find the K-Beauty of a Number - Solution & Explanation
Problem Statement
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.
0is 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(takingnumas a string)
Approach Overview
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 1: Sliding Window Approach
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.
Complexity
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.
Approach 2: Direct Substring Calculation and Check
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.
Complexity
Time complexity: O(n*k).
Space complexity: O(1), as it uses linear space.
Approach 3: Enumeration
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).
Code
Python
Java
C++
Go
TypeScript
Approach 4: Sliding Window
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2269. Find the K-Beauty of a Number (Leetcode Easy) • Programming Live with Larry • 2,427 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the K-Beauty of a Number easy or hard?
Find the K-Beauty of a Number Python/Java solution
How to solve Find the K-Beauty of a Number in O(n)?
What is the best approach for Find the K-Beauty of a Number?
Is Find the K-Beauty of a Number asked at Google/Amazon/Meta?
What data structure is used in Find the K-Beauty of a Number?
What is the time complexity of Find the K-Beauty of a Number?
Ready to solve this problem?
Practice Find the K-Beauty of a Number with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor