Find the K-Beauty of a Number - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: num = 240, k = 2

› Output: 2

💡 Note: Substrings of length 2: "24" and "40". Both 24 and 40 divide 240 evenly, so k-beauty is 2.

Example 2 — With Leading Zero

$ Input: num = 430, k = 2

› Output: 1

💡 Note: Substrings: "43", "30". 430 ÷ 43 = 10 (exact division), but 430 ÷ 30 = 14.333... (not exact). Only "43" divides evenly, so k-beauty is 1.

Example 3 — No Valid Divisors

$ Input: num = 123, k = 3

› Output: 1

💡 Note: Only substring is "123". Since 123 ÷ 123 = 1, it divides itself, so k-beauty is 1.

Constraints

1 ≤ num ≤ 10⁹
1 ≤ k ≤ num.length

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12

The key insight is to convert the number to a string and use a sliding window to extract all k-length substrings, then test each for divisibility. The sliding window approach provides clean code structure. Time: O(n), Space: O(n) where n is the number of digits.

Common Approaches

✓ Brute Force with String Conversion

⏱️ Time: O(n) Space: O(n)

Convert the number to a string, then iterate through all possible k-length substrings. For each substring, convert it back to an integer and check if it's a valid divisor of the original number.

Sliding Window Optimization

⏱️ Time: O(n) Space: O(n)

Convert the number to string once, then use a sliding window of size k to extract each substring efficiently. This approach maintains the same time complexity but provides cleaner code structure.

Brute Force with String Conversion — Algorithm Steps

Step 1: Convert num to string
Step 2: Extract each k-length substring
Step 3: Convert substring to integer and check if it divides num
Step 4: Count valid divisors

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to String

Convert number 240 to string "240"

Extract Substrings

Get all k=2 length substrings: "24", "40"

Check Divisibility

Test if 24 and 40 divide 240

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int num, int k) {
    char numStr[20];
    sprintf(numStr, "%d", num);
    int len = strlen(numStr);
    int count = 0;
    
    for (int i = 0; i <= len - k; i++) {
        char substring[20];
        strncpy(substring, numStr + i, k);
        substring[k] = '\0';
        int substringNum = atoi(substring);
        
        if (substringNum != 0 && num % substringNum == 0) {
            count++;
        }
    }
    
    return count;
}

int main() {
    int num, k;
    scanf("%d %d", &num, &k);
    printf("%d\n", solution(num, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string of length n, where n is number of digits

✓ Linear Growth

Space Complexity

O(n)

String representation of the number takes O(n) space

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the K-Beauty of a Number - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with String Conversion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler