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, a self-dividing number cannot contain the digit zero.

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. Are the lower and upper bounds inclusive?
   • Yes, they are inclusive according to the problem statement.
2. What happens if there are no self-dividing numbers in the given range?
   • Return an empty list.
3. What range of values can left and right take?
   • Typically, the constraints would be provided in a real interview. In the absence of explicit constraints, assume reasonable limits as per the problem statement, e.g., 1 <= left <= right <= 10000.

Strategy

1. Iterate through the range: For each number within the given range (left to right), check if it is a self-dividing number.
2. Check if a number is self-dividing:
   • Extract each digit of the number.
   • Check if the number is divisible by each of its digits.
   • Ensure that none of the digits is zero.
3. Add to the result list: If the number passes the self-dividing check, add it to the result list.
4. Edge cases to handle:
   • Numbers containing the digit zero should not be considered self-dividing.

Code

Here’s the Java code to solve the problem:

import java.util.ArrayList;
import java.util.List;

public class SelfDividingNumbers {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<>();
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.add(num);
            }
        }
        return result;
    }

    private boolean 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;
    }
}

Time Complexity

• Checking if a number is self-dividing: For a number with (k) digits, it takes (O(k)) time to check if it’s self-dividing (since we need to check each digit).
• Iterating through the range: If the range from left to right includes n numbers, we perform the above check for each number.

Hence, the total time complexity is proportional to the number of digits processed over all numbers in the range, which can be approximated as (O(n \cdot k)), where (n) is the size of the range and (k) is the number of digits per number. If we assume (k) is upper-bounded by a small constant (since typical constraints would involve reasonably small numbers), the complexity can be simplified to (O(n)).

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?