Skip to main content

728. Self Dividing Numbers

easy

Find every integer in a range that is divisible by each of its own digits. A clean simulation problem — easy to write, easy to over-engineer.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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).

Constraints

  • 1 <= left <= right <= 10^4

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk every integer i in [left, right]. For each, decompose i digit-by-digit and check divisibility.

Hint 2

Two early-exit conditions in the digit loop: if a digit is 0, fail; if i is not divisible by the digit, fail.

Hint 3

Use a helper isSelfDividing(n) that does the digit loop and returns a bool.

Hint 4

Time per check is O(log10 n). Total O((right - left) * log10 right) which is fast enough for the constraints.

Solution approach

Reveal approach

For each integer n in [left, right], call a helper isSelfDividing(n). The helper copies n into a working variable x, then loops: digit = x % 10; if digit == 0 or n % digit != 0 return false; x /= 10; stop when x == 0. If the loop completes, return true. Collect every n that passes into the answer list. O((right - left) * log10(right)) time, O(1) extra space beyond the output. The digit == 0 short-circuit is critical — otherwise you'd hit a divide-by-zero. The n % digit check uses the ORIGINAL n, not the loop variable x — that's the bug interviewers look for.

Complexity

Time
O((right - left) * log n)
Space
O(1)

Related patterns

  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple

More Math practice problems

See all Math problems →