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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Self Dividing Numbers and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →