LeetCode 2269 - Find the K-Beauty of a Number

LeetCode Problem 2269

Difficulty: 🟢 Easy
Topics: Math, String, Sliding Window

Solution

Problem Understanding

The problem asks us to calculate the k-beauty of a given integer num. To do this, we treat num as a string and examine every possible contiguous substring of length k. For each substring, we interpret it as an integer and check whether it divides the original number num evenly. The final answer is simply the number of valid substrings that satisfy this divisibility condition.

In other words, we are sliding a window of size k across the string representation of num. Every window gives us a substring of exactly k digits. We convert that substring into a number and check two conditions:

1. The substring value must not be 0, because division by zero is undefined.
2. The substring value must divide num evenly, meaning num % substring_value == 0.

The input consists of:

• num, the integer whose k-beauty we want to compute.
• k, the required substring length.

The output is a single integer representing how many valid length-k substrings are divisors of num.

The constraints are relatively small:

• 1 <= num <= 10^9
• 1 <= k <= len(str(num))

Since num is at most 10^9, its string representation contains at most 10 digits. This means the total number of substrings we examine is very small. Even a straightforward solution would be efficient enough, but we can still write a clean sliding window implementation.

There are several edge cases worth considering upfront. A substring may evaluate to 0, for example "00" or "0", and we must explicitly avoid division by zero. Leading zeros are allowed, meaning a substring like "04" is valid and should be interpreted as integer 4. We must also correctly handle the case where k equals the entire length of num, which means there is only one substring to examine. Finally, repeated substrings should each be counted independently if they appear in different positions.

Approaches

Brute Force Approach

The most direct solution is to generate every substring of length k, convert it into an integer, and test whether it divides num.

We first convert num into a string so we can easily extract substrings. Then, for every starting index i, we take the substring s[i:i+k], convert it to an integer, and check:

• Is the value nonzero?
• Does it divide num evenly?

If both conditions are true, we increment our answer.

This approach is correct because it explicitly checks every possible substring exactly once and applies the problem definition directly. Since the maximum length of num is only around 10 digits, this is already efficient enough.

The only inefficiency comes from repeatedly slicing strings and converting substrings into integers. However, given the constraints, this cost is negligible.

Key Insight for an Optimal Approach

The problem naturally fits a sliding window pattern because we examine every contiguous substring of fixed length k.

Instead of thinking of the task as repeatedly generating independent substrings, we can think of moving a window of size k across the string representation of num. At each position, we evaluate the current window and move one character forward.

Although we still use substring slicing in practice because the input size is tiny, conceptually this is a sliding window problem since we process all fixed-length contiguous segments exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(k)	Extracts and converts every substring independently
Optimal	O(n × k)	O(k)	Sliding window over fixed-size substrings

Here, n represents the number of digits in num. Since n <= 10, the runtime is effectively constant in practice.

Algorithm Walkthrough

1. Convert num into a string so we can access its digits and extract substrings easily.
2. Initialize a counter count = 0. This variable will track how many substrings satisfy the divisor condition.
3. Iterate through every possible starting position of a length-k substring. Since the substring length is fixed, the valid range is from index 0 to len(num_string) - k.
4. Extract the current substring using slicing, num_string[i:i+k].
5. Convert the substring into an integer. This automatically handles leading zeros correctly. For example, "04" becomes 4.
6. Check whether the substring value is nonzero. This step prevents division by zero errors.
7. If the value is nonzero, check whether it divides num evenly using the modulus operator:

num % substring_value == 0 8. If the condition is true, increment the counter. 9. After processing all substrings, return the final count.

Why it works

The algorithm works because it systematically checks every valid substring of length k exactly once. For each substring, it directly verifies the exact condition required by the problem definition, whether the substring represents a nonzero divisor of num. Since no substring is skipped or counted multiple times incorrectly, the final count is guaranteed to equal the k-beauty of num.

Python Solution

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        num_string = str(num)
        count = 0

        for i in range(len(num_string) - k + 1):
            substring_value = int(num_string[i:i + k])

            if substring_value != 0 and num % substring_value == 0:
                count += 1

        return count

The implementation begins by converting num into a string, allowing us to easily extract contiguous substrings. We then initialize count to track how many valid divisors we find.

The loop iterates over every possible starting position for a substring of length k. At each step, we extract the substring and convert it into an integer. This conversion naturally handles leading zeros, which the problem explicitly allows.

Before performing divisibility testing, we check whether the substring value is zero. This prevents invalid division operations. If the substring is nonzero and divides num evenly, we increment the answer.

Finally, after all substrings have been checked, we return the accumulated count.

Go Solution

func divisorSubstrings(num int, k int) int {
	numStr := strconv.Itoa(num)
	count := 0

	for i := 0; i <= len(numStr)-k; i++ {
		substringValue, _ := strconv.Atoi(numStr[i : i+k])

		if substringValue != 0 && num%substringValue == 0 {
			count++
		}
	}

	return count
}

The Go implementation follows exactly the same logic as the Python version. We convert the integer into a string using strconv.Itoa, then iterate through all valid substring positions.

One Go-specific detail is integer parsing. We use strconv.Atoi to convert substrings into integers. The returned error is safely ignored because every substring consists only of numeric characters from the original number.

To compile successfully in LeetCode, remember to include:

import "strconv"

Unlike Python, Go does not have built-in integer-to-string conversion through str(), so we explicitly use the strconv package.

Worked Examples

Example 1

Input: num = 240, k = 2

String representation:

"240"

We examine every substring of length 2.

Iteration	Substring	Integer Value	Divides 240?	Count
1	"24"	24	Yes, 240 % 24 == 0	1
2	"40"	40	Yes, 240 % 40 == 0	2

Final answer:

2

Example 2

Input: num = 430043, k = 2

String representation:

"430043"

We examine every substring of length 2.

Iteration	Substring	Integer Value	Divides 430043?	Count
1	"43"	43	Yes	1
2	"30"	30	No	1
3	"00"	0	Invalid, cannot divide	1
4	"04"	4	No	1
5	"43"	43	Yes	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × k)	We examine n - k + 1 substrings, each slicing and conversion costs up to O(k)
Space	O(k)	Temporary substring storage requires up to k characters

The runtime depends on the number of substrings and the cost of converting each substring into an integer. Since each substring contains at most k digits, conversion takes O(k) time. However, because num has at most 10 digits, this runtime is extremely small in practice.

The auxiliary space complexity is O(k) because substring extraction creates temporary strings of length at most k.

Test Cases

solution = Solution()

# Provided examples
assert solution.divisorSubstrings(240, 2) == 2  # Example 1
assert solution.divisorSubstrings(430043, 2) == 2  # Example 2

# Single digit number
assert solution.divisorSubstrings(5, 1) == 1  # 5 divides itself

# k equals full length of number
assert solution.divisorSubstrings(120, 3) == 1  # Entire number divides itself

# Contains zero substring
assert solution.divisorSubstrings(100, 1) == 1  # "1" works, "0" ignored

# Leading zero substring
assert solution.divisorSubstrings(104, 2) == 1  # "04" becomes 4 and divides 104

# No valid divisors
assert solution.divisorSubstrings(123, 2) == 0  # Neither 12 nor 23 divides 123

# Repeated valid substrings
assert solution.divisorSubstrings(111, 1) == 3  # Every "1" divides 111

# Multiple zeros
assert solution.divisorSubstrings(1000, 2) == 1  # "10" valid, "00" invalid

# Maximum style input
assert solution.divisorSubstrings(999999999, 1) == 9  # Every 9 divides number

Test	Why
240, 2	Verifies the first provided example
430043, 2	Verifies leading zeros and zero handling
5, 1	Smallest possible input
120, 3	Tests when k equals number length
100, 1	Ensures zero substrings are ignored
104, 2	Validates leading zero parsing
123, 2	Checks behavior when no substring divides
111, 1	Confirms repeated substrings are counted separately
1000, 2	Tests multiple zero substrings
999999999, 1	Stresses repeated divisor counting

Edge Cases

One important edge case occurs when a substring evaluates to 0. Since zero cannot divide any number, attempting num % 0 would cause an error. This can happen with inputs such as 430043, where the substring "00" appears. The implementation explicitly checks substring_value != 0 before attempting division, ensuring safe execution.

Another important case is leading zeros. The problem allows substrings like "04" or "001". A careless implementation might incorrectly reject these or treat them as strings instead of numeric values. By converting the substring to an integer using int() in Python or strconv.Atoi() in Go, "04" correctly becomes 4, allowing valid divisibility checks.

A third edge case occurs when k equals the total number of digits in num. In this situation, only one substring exists, the entire number itself. Since any nonzero number divides itself, the result will always be 1. The loop bounds handle this naturally because len(num_string) - k + 1 becomes 1, producing exactly one iteration.