Find the K-Beauty of a Number

Easy
780.

Find the K-Beauty of a Number

Find the K-Beauty of a Number is an easy coding problem on strings, math and sliding window, asked in Amazon, Adobe and Infosys interviews.

The k-beauty of num is the number of substrings of length k in its decimal representation that are divisors of num. A substring whose value is 0 never counts, and leading zeros are allowed.

Return the k-beauty of num.

Example 1

Input
num = 240, k = 2
Output
2
Explanation
"24" and "40" both divide 240.

Example 2

Input
num = 430043, k = 2
Output
2
Explanation
"43" appears twice and divides 430043; "30", "00" and "04" do not.

Example 3

Input
num = 1, k = 1
Output
1

Constraints

  • 1 <= num <= 1000000000
  • 1 <= k <= number of digits in num
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @param {number} k
 * @return {number}
 */
var divisorSubstrings = function(num, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the K-Beauty of a Number — Problem & Solution

Find the K-Beauty of a Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the K-Beauty of a Number is an easy coding problem on strings, math and sliding window, asked in Amazon, Adobe and Infosys interviews.

  • Difficulty: Easy
  • Topics: Strings, Math, Sliding Window
  • Asked at: Amazon, Adobe, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The k-beauty of num is the number of substrings of length k in its decimal representation that are divisors of num. A substring whose value is 0 never counts, and leading zeros are allowed.

Return the k-beauty of num.

Example 1

Input: num = 240, k = 2
Output: 2
Explanation: "24" and "40" both divide 240.

Example 2

Input: num = 430043, k = 2
Output: 2
Explanation: "43" appears twice and divides 430043; "30", "00" and "04" do not.

Example 3

Input: num = 1, k = 1
Output: 1

Constraints

  • 1 <= num <= 1000000000
  • 1 <= k <= number of digits in num

Hints for Find the K-Beauty of a Number

  1. Hint 1

    Work on the decimal string — the substrings are windows over its digits.

  2. Hint 2

    A window's value can be rolled forward, but at these sizes parsing each window directly is fine.

  3. Hint 3

    Guard against a window that parses to zero: division by it is undefined, and it never divides anything.

How to solve Find the K-Beauty of a Number

Convert the number to a string and slide a window of k digits over it, testing each window's value for divisibility.

Approach

  1. Render num as a decimal string s.
  2. For every start i with i + k <= |s|, parse s[i … i+k-1] as an integer.
  3. Count it when it is non-zero and divides num.

Why it works

There are at most 10 digits, so at most 10 windows; each parse is bounded work. The zero guard matters because leading zeros are permitted, so a window such as "00" really does have value 0.

Complexity

  • Time — O(d · k) where d is the digit count
  • Space — O(d)

Pitfalls

  • Dividing by a zero-valued window crashes or throws in most languages.
  • Stripping leading zeros changes the window's length and is not what the problem asks.
  • num fits int, but a k-digit window of a 10-digit number can too — no widening is needed.

Reference solution

Python

def divisorSubstrings(num: int, k: int) -> int:
    s = str(num)
    count = 0
    for i in range(len(s) - k + 1):
        v = int(s[i:i + k])
        if v != 0 and num % v == 0:
            count += 1
    return count

Java

public static int divisorSubstrings(int num, int k) {
    String s = Integer.toString(num);
    int count = 0;
    for (int i = 0; i + k <= s.length(); i++) {
        int v = Integer.parseInt(s.substring(i, i + k));
        if (v != 0 && num % v == 0) count++;
    }
    return count;
}

C++

int divisorSubstrings(int num, int k) {
    string s = to_string(num);
    int count = 0;
    for (int i = 0; i + k <= (int) s.size(); i++) {
        int v = stoi(s.substr(i, k));
        if (v != 0 && num % v == 0) count++;
    }
    return count;
}

JavaScript

var divisorSubstrings = function(num, k) {
    var s = String(num);
    var count = 0;
    for (var i = 0; i + k <= s.length; i++) {
        var v = parseInt(s.substring(i, i + k), 10);
        if (v !== 0 && num % v === 0) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sliding Window Technique