Get started

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

The k-beauty of num is the number of substrings of length k in its decimal representation that are divisors of num.

  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue