Find the K-Beauty of a Number

Easy

Quora

1 view

Topics:

StringsSliding Windows

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.
0 is 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 <= 10⁹
1 <= k <= num.length (taking num as a string)

Try coding it in LeetCode

Find the K-Beauty of a Number

Easy

Quora

1 view

Topics:

StringsSliding Windows

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.
0 is 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 <= 10⁹
1 <= k <= num.length (taking num as a string)

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `num` and `k`? Can `num` or `k` be zero or negative?
If `k` is larger than the number of digits in `num`, what should the function return?
If a k-digit consecutive number from `num` is zero, should it be considered a divisor (even though division by zero is undefined)?
Should overlapping k-digit consecutive numbers be counted multiple times if they are k-beauties? For example, if num = 111 and k = 1, should the '1' be counted three times?
Can `num` be represented as a string, or should I perform integer arithmetic to extract the k-digit numbers?

Brute Force Solution

Approach

The brute force method for finding the K-beauty of a number involves checking every possible substring of length K. We go through the number digit by digit, and for each substring, we see if it divides the original number evenly.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the number.
Grab the first K digits as a substring.
Check if this substring (treated as a number) is a valid divisor (not zero).
If the substring is a valid divisor, check if the original number is perfectly divisible by this substring.
If it is, increase our beauty count.
Move one digit to the right, and grab the next K digits as a substring.
Repeat steps 3-5.
Keep repeating this process until you reach the end of the number, making sure you have K digits to form a substring at each step.
The final beauty count is the number of substrings that divide the original number.

Code Implementation

def find_k_beauty(number, k_digits):
    number_string = str(number)
    number_string_length = len(number_string)
    beauty_count = 0

    for index in range(number_string_length - k_digits + 1):
        # Extract substring of length k_digits
        substring = number_string[index:index + k_digits]
        substring_as_integer = int(substring)

        # Avoid division by zero
        if substring_as_integer == 0:
            continue

        # Check if substring divides the number
        if number % substring_as_integer == 0:
            beauty_count += 1

    return beauty_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number once. In each iteration, a substring of length K is extracted which is considered a constant time operation since K is fixed. Then, it performs a division to check for divisibility, also a constant time operation. Since the algorithm processes at most n-K+1 substrings, where n is the number of digits in the input number, the overall time complexity is O(n).

Space Complexity

O(1) – The provided algorithm primarily uses a sliding window approach to extract substrings of length K from the input number. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. The algorithm only uses a few constant space variables to store the number (potentially implicitly as a string or integer), the current substring, and the beauty count. Therefore, the space complexity is constant and independent of the input size N (the number of digits in the input number).

Optimal Solution

Approach

The goal is to count how many substrings of a number can evenly divide the original number. Instead of checking every possible substring, we extract and check the divisibility of substrings efficiently to avoid redundant calculations.

Here's how the algorithm would work step-by-step:

Convert the number to a string so we can easily look at different parts of it.
Go through each possible length for our substrings, starting from a length of 1 up to the full length of the number.
For each substring length, move across the string one digit at a time to create substrings.
Convert each substring back into a number.
Check if the substring number is greater than zero and if the original number can be divided evenly by the substring number.
If it divides evenly, increase the count.
Once we've checked all possible substrings, return the final count.

Code Implementation

def find_k_beauty(number, substring_length):
    number_string = str(number)
    string_length = len(number_string)
    k_beauty_count = 0

    # Iterate through all possible substring lengths.
    for current_substring_length in range(1, substring_length + 1):
        for i in range(string_length - current_substring_length + 1):
            substring = number_string[i:i + current_substring_length]

            # Convert the substring back to an integer
            substring_number = int(substring)

            # Avoid division by zero and check divisibility
            if substring_number > 0:
                if number % substring_number == 0:

                    # Count if the substring divides evenly into the number
                    k_beauty_count += 1

    return k_beauty_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm converts the input number to a string of length n. It then iterates through all possible substring lengths from 1 to n using an outer loop. For each substring length, an inner loop iterates through the string to extract all substrings of that length. The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs approximately n times in the worst case. Therefore, the time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm primarily utilizes a few integer variables for loop counters, substring length, and the count of K-beauty numbers. The conversion of the number to a string is part of the input transformation and doesn't represent significant auxiliary space. The substrings are derived directly within the loops without storing them in a separate collection. Therefore, the space used remains constant irrespective of the input number's length N, leading to O(1) space complexity.

Edge Cases

Case	How to Handle
k is zero	Return 0 because a 0-digit number is meaningless in this context.
k is greater than the number of digits in num	Return 0 because no k-digit number can be formed.
num is zero	If k is 1, return 1, otherwise return 0 as any k-digit number (k>1) cannot be extracted from zero.
num is negative	Convert num to its absolute value since divisibility is checked regardless of sign.
k is 1 and num has multiple digits of 0	The solution correctly identifies each zero digit as a divisor if num is divisible by 0.
k-digit substring is 0	Avoid division by zero by checking if the k-digit number is zero before performing the division.
Integer overflow when extracting k-digit substrings	Use a data type capable of holding large integers, like long, to avoid potential overflow during substring extraction and conversion.
Large num with a small k (e.g., num = 1234567890, k = 1)	Ensure the solution's time complexity is linear with respect to the number of digits in num to handle large numbers efficiently.