Leetcode 2269: Find the K-Beauty of a Number

Input: You are given an integer `num` and an integer `k`, where `num` is a number and `k` is the length of substrings to consider.

Example: num = 150, k = 2

Constraints:

• 1 <= num <= 10^9

• 1 <= k <= num.length (considering num as a string)

Output: Return the k-beauty of the number `num`, which is the number of valid divisors formed by its substrings of length `k`.

Example: Output: 2

Constraints:

Goal: To compute the number of divisors that can be formed by substrings of length `k` from the number `num`. These substrings should divide `num` without a remainder.

Steps:

• Convert `num` to a string and extract all substrings of length `k`.

• Check each substring to see if it is a valid divisor of `num`.

• Count how many substrings are divisors and return that count.

Goal: The solution must handle large inputs efficiently and work within the given constraints.

Steps:

• Avoid dividing by zero as 0 is not a valid divisor.

Assumptions:

• The input number `num` will always be positive, and the substring length `k` will not exceed the length of `num`.

• Input: num = 150, k = 2

• Explanation: The possible substrings of length 2 are '15', '50', '00'. Among them, '15' and '50' are divisors of 150. Therefore, the k-beauty is 2.

• Input: num = 430043, k = 3

• Explanation: The possible substrings of length 3 are '430', '300', '000', '043', '430', '043'. Only '430' is a divisor of 430043. Therefore, the k-beauty is 1.

Approach: To solve this problem, we can iterate through the string representation of `num`, extract substrings of length `k`, convert them to integers, and check if they are divisors of `num`.

Observations:

• We need to extract all possible substrings of length `k` from the string representation of `num`.

• Each extracted substring must be checked to see if it divides the original number `num`.

• This can be done efficiently by iterating through the string and checking divisibility. The complexity is directly related to the number of substrings we need to check.

Steps:

• Convert the integer `num` to a string.

• Iterate over the string, extract all substrings of length `k`.

• For each substring, convert it to an integer and check if it divides `num` without a remainder.

• Count the valid divisors and return that count.

Empty Inputs:

• There will always be at least one digit in the input `num`.

Large Inputs:

• The solution should handle large numbers efficiently, up to the constraint limits of 10^9.

Special Values:

• Ensure that substrings representing '0' do not result in division errors since 0 is not a valid divisor.

Constraints:

• The solution should work within the time limits and handle large numbers efficiently.

int divisorSubstrings(int num, int k) {
    int res = 0, cur = 0, pow = 1;
    for (int n = num; n > 0; n /= 10) {
        cur += (n % 10) * pow;
        if (--k > 0)
            pow *= 10;
        else {
            res += cur && !(num % cur);
            cur /= 10;
        }
    }
    return res;        
}

1 : Function Declaration

int divisorSubstrings(int num, int k) {

This is the function header that defines `divisorSubstrings`, which takes two parameters: an integer `num` and an integer `k`, and returns the count of valid divisors.

2 : Variable Initialization

    int res = 0, cur = 0, pow = 1;

Initializes the variables: `res` to store the result, `cur` to store the current substring, and `pow` to calculate the place value of digits.

3 : Loop Start

    for (int n = num; n > 0; n /= 10) {

Starts a loop that processes each digit of `num` from right to left, using integer division to extract digits.

4 : Update Current Substring

        cur += (n % 10) * pow;

Extracts the last digit of `n` and adds it to `cur`, multiplied by `pow` to account for the place value of the digit.

5 : Condition to Continue Substring Building

        if (--k > 0)

Decreases `k` and checks if there are still digits to be added to the current substring (i.e., if the substring length is less than `k`).

6 : Place Value Update

            pow *= 10;

If the substring is not yet of length `k`, updates the place value (`pow`) to multiply the next digit by the correct power of 10.

7 : Condition Block for Divisibility Check

        else {

If `k` is 0 (i.e., the substring has reached length `k`), the code block checks if the current substring divides `num`.

8 : Divisibility Check

            res += cur && !(num % cur);

Checks if the current substring `cur` is a divisor of `num`. If so, increments the result `res`. The `cur && !(num % cur)` condition ensures `cur` is non-zero and divides `num` evenly.

9 : Update Current Substring

            cur /= 10;

Removes the last digit from `cur` after the divisibility check to prepare for the next iteration.

10 : Return Statement

    return res;

Returns the final result `res`, which is the count of valid divisors found for `num`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where `n` is the length of the string representation of `num`.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) since we are only storing the result and iterating through the string.

Leetcode 2269: Find the K-Beauty of a Number

Explore →