A self-dividing number is a number that is divisible by every digit it contains.
128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.A self-dividing number is not allowed to contain the digit zero.
Given two integers left and right, return a list of all the self-dividing numbers in the range [left, right] (both inclusive).
Example 1:
Input: left = 1, right = 22 Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]
Example 2:
Input: left = 47, right = 85 Output: [48,55,66,77]
Constraints:
1 <= left <= right <= 104To solve #728 Self Dividing Numbers, iterate through every number in the given range and verify whether it satisfies the self-dividing condition. A number is considered self-dividing if every digit in the number divides the number itself and none of its digits are 0.
The key idea is to extract digits one by one using modulo and division operations. For each digit, check two conditions: the digit should not be 0, and the original number must be divisible by that digit. If any digit fails this check, the number is not self-dividing. If all digits pass, include the number in the result list.
This approach relies on simple arithmetic operations and sequential checks. Since each number is processed independently, the algorithm is straightforward and efficient. The time complexity mainly depends on the size of the range and the number of digits per number, while the space complexity is determined by the output list.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterate through range and check each digit | O(n * d) | O(1) auxiliary (excluding output) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
For each number in the range, check whether it is self dividing by converting that number to a character array (or string in Python), then checking that each digit is nonzero and divides the original number.
This approach involves iterating over each number within the given range. For each number, extract each digit and check if the number is evenly divisible by that digit. If it passes all checks, the number is self-dividing.
Time Complexity: O(n*m), where n is the range and m is the number of digits in each number.
Space Complexity: O(1) since no extra space is used proportional to input size.
1#include <stdio.h>
2#include <stdbool.h>
3
4bool isSelfDividing(int num) {
5 int original = num, digit;
6 while (num > 0) {
7 digit = num % 10;
8 if (digit == 0 || original % digit != 0) {
9 return false;
10 }
11 num /= 10;
12 }
13 return true;
14}
15
16void selfDividingNumbers(int left, int right) {
17 for (int i = left; i <= right; i++) {
18 if (isSelfDividing(i)) {
19 printf("%d ", i);
20 }
21 }
22}
23
24int main() {
25 int left = 1, right = 22;
26 selfDividingNumbers(left, right);
27 return 0;
28}This C solution uses a helper function isSelfDividing to check if each number in the range is a self-dividing number. For each number, we repeatedly extract the last digit and check if it divides the original number evenly. The function returns a boolean indicating if a number is self-dividing.
This approach optimizes the check by making a presumption against numbers containing digit zero immediately. Numbers with digit zero are automatically non-self-divisible. For the rest, we still check each digit, but this could reduce the number of required operations.
Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers.
Space Complexity: O(1).
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Self Dividing Numbers may appear in coding interviews as easy-level screening questions. They test understanding of number manipulation, loops, and edge cases rather than advanced algorithms.
No complex data structure is required for this problem. A simple list or array is sufficient to store the resulting self-dividing numbers, while the digit checks rely only on basic arithmetic operations.
The optimal approach is to iterate through each number in the given range and check its digits using modulo and division. For each digit, ensure it is not zero and that the original number is divisible by it. If all digits satisfy this condition, the number is self-dividing.
Digits with 0 are invalid because division by zero is undefined. Since a self-dividing number must be divisible by each of its digits, any number containing the digit 0 automatically fails the condition.
This C solution skips numbers divisible by 10 entirely, focusing on the rest to identify self-dividing numbers, slightly optimizing computations by reducing unnecessary checks.