Scale Engineer

Self Dividing Numbers

Easy
#0682Time: O(D * log(R)), where D is the number of integers in the range `[left, right]` (i.e., `right - left + 1`), and R is the value of `right`. For each number, we convert it to a string and iterate through its digits. The number of digits in a number `n` is proportional to `log10(n)`. Since `right` is the upper bound, the complexity is dominated by checking numbers near `right`.Space: O(log(R)) for auxiliary space, excluding the output list. This space is used to store the string representation of a number. The output list itself can take up to O(D) space in the worst case, where D is the number of elements in the range.1 company
Patterns
Math
Companies
Epic Systems

Prompt

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.

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 <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each number in the given range [left, right]. For each number, it converts the number to a string to easily access its digits. It then checks if the number is divisible by each of its digits.

Algorithm

  • Initialize an empty list ans to store the self-dividing numbers.
  • Iterate through each number i from left to right.
  • For each number i, check if it is a self-dividing number using a helper function.
  • Helper function isSelfDividing(num):
    • Convert the number num to a string s.
    • Iterate through each character c of the string s.
    • Convert the character c to an integer digit.
    • If digit is 0, return false.
    • If num is not divisible by digit (i.e., num % digit != 0), return false.
    • If the loop completes without returning, it means the number is self-dividing, so return true.
  • If the helper function returns true for i, add i to the ans list.
  • After the loop finishes, return the ans list.

Walkthrough

The algorithm involves a loop that goes from left to right. Inside the loop, for each number num, we first convert it into its string representation. We then iterate through each character of the string. Each character is converted back to an integer digit. Two conditions are checked for each digit:

  1. If the digit is 0, the number is not self-dividing.
  2. If the original number num is not divisible by the digit, it's not self-dividing.

If a number fails either of these checks, we stop processing it and move to the next number in the range. If a number passes the divisibility check for all its digits, it is added to our result list. Finally, the list of self-dividing numbers is returned.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> selfDividingNumbers(int left, int right) {        List<Integer> result = new ArrayList<>();        for (int i = left; i <= right; i++) {            if (isSelfDividing(i)) {                result.add(i);            }        }        return result;    }     private boolean isSelfDividing(int num) {        String s = String.valueOf(num);        for (char c : s.toCharArray()) {            int digit = c - '0';            if (digit == 0) {                return false; // Cannot contain digit 0            }            if (num % digit != 0) {                return false; // Not divisible by one of its digits            }        }        return true;    }}

Complexity

Time

O(D * log(R)), where D is the number of integers in the range `[left, right]` (i.e., `right - left + 1`), and R is the value of `right`. For each number, we convert it to a string and iterate through its digits. The number of digits in a number `n` is proportional to `log10(n)`. Since `right` is the upper bound, the complexity is dominated by checking numbers near `right`.

Space

O(log(R)) for auxiliary space, excluding the output list. This space is used to store the string representation of a number. The output list itself can take up to O(D) space in the worst case, where D is the number of elements in the range.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Directly translates the problem definition into code.

Cons

  • Involves type conversions (integer to string, character to integer), which can be less efficient than pure arithmetic operations.

  • Uses slightly more memory due to the creation of string objects for each number.

Solutions

class Solution { public List < Integer > selfDividingNumbers ( int left , int right ) { List < Integer > ans = new ArrayList <>(); for ( int i = left ; i <= right ; ++ i ) { if ( check ( i )) { ans . add ( i ); } } return ans ; } private boolean check ( int num ) { for ( int t = num ; t != 0 ; t /= 10 ) { int x = t % 10 ; if ( x == 0 || num % x != 0 ) { return false ; } } return true ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem