algoadvance

Leetcode 728. Self Dividing Numbers

Problem Statement

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, note that self-dividing numbers do not include any zero digits.

Given a lower and upper number bound, output a list of every possible self-dividing number, including the bounds if possible.

Example:

Input: left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Clarifying Questions

1. What is the range of inputs for left and right?
   • It can be assumed that left and right are within reasonable integer limits, typically between 1 and 10000.
2. Do we need to handle negative numbers or non-integer inputs?
   • No, as the problem guarantees valid integer inputs between a specified range.
3. What should be returned if left is greater than right?
   • It’s assumed that left <= right as per the problem constraints unless specified otherwise.

Strategy

1. Iterate through each number in the range [left, right].
2. For each number, determine if it is a self-dividing number:
   • Extract each digit of the number.
   • Check if the number is divisible by each of its digits.
   • If any digit is zero or if the number isn’t divisible by any digit, it’s not a self-dividing number.
3. Collect all the self-dividing numbers and return them.

Code

#include <vector>

bool isSelfDividing(int num) {
    int original = num;
    while (num > 0) {
        int digit = num % 10;
        if (digit == 0 || original % digit != 0) {
            return false;
        }
        num /= 10;
    }
    return true;
}

std::vector<int> selfDividingNumbers(int left, int right) {
    std::vector<int> result;
    for (int i = left; i <= right; ++i) {
        if (isSelfDividing(i)) {
            result.push_back(i);
        }
    }
    return result;
}

Time Complexity

• Time Complexity: The time complexity is O((right - left + 1) * d) where d is the number of digits in the maximum number in the range. This simplifies to O(n * log(max_num)) where n is the number of integers in the range and log(max_num) is the number of digits in the largest number.
• Space Complexity: The space complexity is O(1) for the extra space used, but since we are storing results in a vector, it can be considered O(n) where n is the number of self-dividing numbers in the given range.

The above implementation efficiently determines self-dividing numbers within the provided range and ensures optimal performance by using basic arithmetic operations.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?