algoadvance

Leetcode 2520. Count the Digits That Divide a Number

Problem Statement

You are given a positive integer num. Count the number of digits in num that divide num.

A digit divides num if num % digit == 0.

Return the number of digits that divide num.

Clarifying Questions

  1. What is the range of num?
    • It’s mentioned that num is a positive integer. Let’s assume it fits within the range of standard integer types in C++.
  2. What should be done if there is a digit ‘0’ in num?
    • Since ‘0’ cannot divide any number, it should be skipped in the count.
  3. Is it guaranteed that num will be a non-zero positive integer?
    • Yes, it’s explicitly mentioned as a positive integer.

Strategy

  1. Convert the number num to its string representation to easily iterate over each digit.
  2. Initialize a counter to keep track of the number of digits that divide num.
  3. For each digit in the string:
    • Convert the character to its integer form.
    • Check if the digit is not zero and if num is divisible by this digit.
    • If true, increment the counter.
  4. Return the counter’s value after iterating through all digits.

Code

#include <iostream>
#include <string>

int countDigitsThatDivide(int num) {
    std::string numStr = std::to_string(num);
    int count = 0;
    
    for (char c : numStr) {
        int digit = c - '0'; // Convert char to int
        if (digit != 0 && num % digit == 0) {
            count++;
        }
    }
    
    return count;
}

int main() {
    int num = 124; // Example input
    std::cout << "Number of digits in " << num << " that divide the number: " << countDigitsThatDivide(num) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(d), where d is the number of digits in num. This is because we are performing a single pass through each digit in the number.

Space Complexity

The space complexity is O(1) excluding the input and output because we only use a few extra variables regardless of the size of num.

This solution effectively handles the problem requirements and constraints as specified.

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