Problem Description

You are given two integers: num and k. Your task is to find the k-beauty of num.

The k-beauty is calculated by counting how many substrings of num (when treated as a string) satisfy both of these conditions:

1. The substring has exactly k digits in length
2. When converted to an integer, it divides num evenly (i.e., num % substring == 0)

For example, if num = 240 and k = 2:

• The string representation is "240"
• The substrings of length 2 are: "24" and "40"
• Check if each divides 240:
  • 24 divides 240 evenly (240 % 24 = 0) ✓
  • 40 divides 240 evenly (240 % 40 = 0) ✓
• The k-beauty is 2

Important notes to remember:

• Leading zeros in substrings are allowed (e.g., "04" from "2040" is valid)
• If a substring equals 0, it cannot be a divisor (division by zero is undefined)
• You need to check all possible consecutive substrings of length k

The solution approach involves converting num to a string, sliding a window of size k across it to get all substrings, converting each substring back to an integer, and checking if it's a non-zero divisor of num. The code iterates through positions i from 0 to len(s) - k, extracts substring s[i:i+k], converts it to integer t, and increments the counter if t != 0 and num % t == 0.

Intuition

The problem asks us to find substrings of a specific length from a number and check if they divide the original number. The natural way to work with substrings is to convert the number to a string first, since extracting consecutive digits is much easier with string operations than with arithmetic operations.

Once we have the string representation, we need to examine every possible substring of length k. This immediately suggests using a sliding window approach - we can start at position 0 and extract k characters, then move to position 1 and extract k characters, and so on. This ensures we don't miss any valid substrings.

For a string of length n, the last valid starting position for a substring of length k would be at index n - k. This is because we need at least k characters remaining from that position. Therefore, we iterate from index 0 to n - k (inclusive), which in Python range notation is range(len(s) - k + 1).

For each substring we extract, we need to convert it back to an integer to perform the divisibility check. The key insight here is that we must handle two edge cases:

1. The substring might be "00" or "000" etc., which converts to integer 0. We cannot check divisibility by 0.
2. The substring might have leading zeros like "04", which is perfectly valid and converts to integer 4.

The condition if t and num % t == 0 elegantly handles both requirements - it first checks if t is non-zero (since 0 is falsy in Python), and only then checks if it divides num evenly.

This straightforward enumeration approach works well because we're simply checking all possibilities without any complex optimization needed.

Learn more about Math and Sliding Window patterns.

Solution Approach

The solution uses a simple enumeration strategy to check all possible substrings of length k.

Step 1: Convert number to string

s = str(num)

We convert the integer num to a string s to easily extract substrings. This allows us to work with individual digits and consecutive sequences without complex arithmetic operations.

Step 2: Initialize counter

ans = 0

We maintain a counter ans to track how many valid divisors we find.

Step 3: Iterate through all possible starting positions

for i in range(len(s) - k + 1):

We loop through each valid starting position for a substring of length k. The range goes from 0 to len(s) - k (inclusive). For example, if s = "240" and k = 2, we iterate through positions 0 and 1, giving us substrings starting at these positions.

Step 4: Extract and convert substring

t = int(s[i : i + k])

For each position i, we extract a substring of length k using Python's slice notation s[i : i + k]. This substring is then converted back to an integer t. The conversion automatically handles leading zeros - for instance, "04" becomes 4.

Step 5: Check divisibility

if t and num % t == 0:
    ans += 1

We perform two checks:

• t evaluates to True if t != 0 (avoiding division by zero)
• num % t == 0 checks if t divides num evenly

If both conditions are met, we increment our counter.

Step 6: Return the result

return ans

After checking all substrings, we return the total count of valid divisors.

The time complexity is O(n * k) where n is the number of digits in num, since we iterate through n - k + 1 positions and for each position, we extract and convert a substring of length k. The space complexity is O(n) for storing the string representation of num.

Example Walkthrough

Let's trace through the solution with num = 430043 and k = 2.

Step 1: Convert to string

• s = "430043"
• Length of string: 6 digits

Step 2: Determine iteration range

• We need substrings of length k = 2
• Valid starting positions: from index 0 to len(s) - k = 6 - 2 = 4
• So we'll check positions 0, 1, 2, 3, and 4

Step 3: Extract and check each substring

Position 0: s[0:2] = "43"

• Convert to integer: t = 43
• Check: Is 43 ≠ 0? Yes. Does 430043 % 43 = 0?
• 430043 ÷ 43 = 10001, so yes!
• Counter: ans = 1

Position 1: s[1:3] = "30"

• Convert to integer: t = 30
• Check: Is 30 ≠ 0? Yes. Does 430043 % 30 = 0?
• 430043 ÷ 30 = 14334.766..., so no
• Counter remains: ans = 1

Position 2: s[2:4] = "00"

• Convert to integer: t = 0
• Check: Is 0 ≠ 0? No (division by zero not allowed)
• Counter remains: ans = 1

Position 3: s[3:5] = "04"

• Convert to integer: t = 4 (leading zero is handled)
• Check: Is 4 ≠ 0? Yes. Does 430043 % 4 = 0?
• 430043 ÷ 4 = 107510.75, so no
• Counter remains: ans = 1

Position 4: s[4:6] = "43"

• Convert to integer: t = 43
• Check: Is 43 ≠ 0? Yes. Does 430043 % 43 = 0?
• 430043 ÷ 43 = 10001, so yes!
• Counter: ans = 2

Result: The k-beauty of 430043 is 2 (substrings "43" at positions 0 and 4 both divide 430043 evenly).

Solution Implementation

Time and Space Complexity

Time Complexity: O(log num × k)

The algorithm converts the number to a string, which has length O(log num) (the number of digits in base 10). Then it iterates through all possible substrings of length k, which gives us O(log num - k + 1) iterations, simplifying to O(log num) iterations. In each iteration, we extract a substring of length k using slicing s[i:i+k], which takes O(k) time, and convert it to an integer, which also takes O(k) time. The modulo operation takes O(1) time. Therefore, the overall time complexity is O(log num × k).

Space Complexity: O(log num + k)

The space complexity consists of:

• The string representation s of the number, which requires O(log num) space to store all digits
• The substring s[i:i+k] created during slicing, which requires O(k) space
• The integer t and other variables use O(1) space

Since these space requirements don't nest but rather add up, the total space complexity is O(log num + k).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Division by Zero Error

The most critical pitfall is forgetting to check if the substring value equals zero before performing the modulo operation. When a substring like "00" or "000" is converted to an integer, it becomes 0, and num % 0 will raise a ZeroDivisionError.

Incorrect Code:

for i in range(len(num_str) - k + 1):
    substring_value = int(num_str[i:i + k])
    if num % substring_value == 0:  # ❌ Crashes when substring_value is 0
        count += 1

Correct Approach:

for i in range(len(num_str) - k + 1):
    substring_value = int(num_str[i:i + k])
    if substring_value != 0 and num % substring_value == 0:  # ✓ Check for zero first
        count += 1

2. Incorrect Range Calculation

Another common mistake is using the wrong range for iteration, which either misses the last valid substring or goes out of bounds.

Incorrect Code:

# Missing the last valid substring
for i in range(len(num_str) - k):  # ❌ Should be len(num_str) - k + 1
    substring = num_str[i:i + k]

# Going out of bounds
for i in range(len(num_str)):  # ❌ Will create incomplete substrings at the end
    substring = num_str[i:i + k]

Correct Approach:

for i in range(len(num_str) - k + 1):  # ✓ Includes all valid positions
    substring = num_str[i:i + k]

3. Type Confusion with Boolean Check

While Python allows if substring_value as shorthand for if substring_value != 0, this can be confusing and less readable, especially for those coming from other languages.

Less Clear:

if substring_value and num % substring_value == 0:  # Works but may confuse readers
    count += 1

More Explicit:

if substring_value != 0 and num % substring_value == 0:  # ✓ Clear intent
    count += 1

4. Edge Case: k Equals String Length

When k equals the length of the number's string representation, there's only one substring to check (the entire number itself). The code handles this correctly, but developers might overthink and add unnecessary special case handling.

Unnecessary Complexity:

if k == len(num_str):
    return 1 if num % num == 0 else 0  # ❌ Redundant special case
else:
    # regular logic

The standard iteration approach already handles this case correctly when range(len(num_str) - k + 1) produces range(1), giving exactly one iteration.