algoadvance

Given an integer num and an integer k, the k-beauty of num is defined as the count of distinct integers of length k that are a contiguous substring of num and are divisible by k.

Given an integer num and an integer k, return the k-beauty of num.

Clarifying Questions

1. Input Data Types?
   • num: A positive integer.
   • k: A positive integer.
2. Output Data Type?
   • The function should return an integer, which is the k-beauty of num.
3. Examples for Better Understanding?
   • Example:

     Input: num = 240, k = 2
     Output: 2
     Explanation: The substrings of length 2 are "24" and "40". Both "24" and "40" are divisible by 2.
     

4. Edge Cases?
   • If num has length less than k, return 0.
   • Handle cases where num contains zeros or leading zeros.

Strategy

1. Convert the number to a string to facilitate slicing.
2. Iterate over the number with a sliding window of size k.
3. Extract each substring, convert it to an integer, check divisibility by k.
4. Collect the divisible substrings in a set to ensure uniqueness.
5. Return the size of the set.

Code

Here’s the Python code to solve the problem:

def find_k_beauty(num: int, k: int) -> int:
    num_str = str(num)
    n = len(num_str)
    
    if k > n:
        return 0
    
    k_beauty_set = set()
    
    for i in range(n - k + 1):
        substring = num_str[i:i + k]
        sub_num = int(substring)
        
        if sub_num % k == 0:
            k_beauty_set.add(sub_num)
            
    return len(k_beauty_set)

# Example usage:
num = 240
k = 2
print(find_k_beauty(num, k))  # Output: 2

Time Complexity

• Converting the number to a string takes O(d) time, where d is the number of digits in num.
• The loop runs n - k + 1 times, where n is the number of digits in num. Each iteration involves slicing the string and converting to an integer, both of which are O(k) operations. Thus, the overall complexity of the loop is O((n - k + 1) * k).
• In the worst case, the overall time complexity is O(d * k).

Space Complexity

• The space complexity is O(d) for storing the string representation of the number and additional space for the set to hold unique k-beauties which, in the worst case, also holds O(d) elements.
• Thus, the space complexity is O(d).

Feel free to ask further clarifying questions or for additional test cases!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?