We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the K-Beauty of a Number

Number: 1430

Difficulty: Easy

Paid? No

Companies: Quora, Postmates

Problem Description

Given an integer num and an integer k, treat num as a string and consider every contiguous substring of length k. The k-beauty of num is defined as the count of those substrings that, when converted to an integer (allowing leading zeros), are non-zero divisors of num.

Key Insights

  • Use a sliding window of size k over the string representation of num to extract substrings.
  • Convert each substring to an integer while handling leading zeros.
  • Avoid division by zero by checking if the integer value is non-zero.
  • Check if num is divisible by the substring value and count it if true.

Space and Time Complexity

Time Complexity: O(m * k), where m is the length of the string representation of num. (Since for each of the m - k + 1 substrings, the conversion takes O(k) time.) Space Complexity: O(m), for storing the string representation of num.

Solution

The solution involves converting the integer num to a string and then iterating over all contiguous substrings of length k using a sliding window technique. For each substring, convert it to an integer and check if it is non-zero and a divisor of num. Increment the counter when both conditions are met. The approach efficiently processes each substring in linear time relative to the number of substrings.

Code Solutions

# Function to find k-beauty of a number
def divisorSubstrings(num, k):
    num_str = str(num)  # Convert the number to a string
    count = 0  # Initialize the count of valid substrings
    # Iterate over all substrings of length k
    for i in range(len(num_str) - k + 1):
        substring = num_str[i:i+k]  # Extract the substring of length k
        divisor = int(substring)  # Convert the substring to an integer
        # Check that divisor is not zero and divides num exactly
        if divisor != 0 and num % divisor == 0:
            count += 1  # Increment count if conditions are met
    return count

# Example usage:
print(divisorSubstrings(240, 2))  # Expected output: 2
← Back to All Questions