algoadvance

Leetcode 2269. Find the K

Problem Statement

You are given a string num representing a positive integer and an integer k. The k-beauty of num is defined as the number of substrings of num of length k that meet the following criteria:

  1. The substring is a positive integer.
  2. It is divisible by k.

Find and return the k-beauty of num.

Clarifying Questions

  1. What is the range of num and k?
    • For instance, can num have up to 10^6 digits, and is k in the range of [1, |num|]?
  2. Are there any assumptions or constraints regarding invalid inputs or edge cases like k > |num|?
  3. How should edge cases be handled, such as when num has leading zeros?

Code

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int divisorSubstrings(string num, int k) {
        int count = 0;
        int n = num.size();
        
        for (int i = 0; i <= n - k; i++) {
            string substring = num.substr(i, k);
            int val = stoi(substring);
            
            if (val > 0 && stoi(num) % val == 0) {
                count++;
            }
        }
        
        return count;
    }
};

int main() {
    Solution sol;
    string num = "240"; // Example input (Adjust as needed)
    int k = 2;          // Example input (Adjust as needed)
    cout << sol.divisorSubstrings(num, k) << endl; // Output: 2 (depends on example)
    return 0;
}

Strategy

  1. Initialize a counter to keep track of the k-beauty.
  2. Loop through the string num and extract every substring of length k.
  3. Convert each substring to an integer.
  4. Check if the integer is a positive integer and if it divides the original number (note that the substring must be a valid number and should not have leading zeros unless the substring itself is “0”).
  5. Increment the counter if the substring meets the criteria.
  6. Return the counter as the final k-beauty of the number.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI