Skip to main content
Talentd

Self Dividing Numbers - Solution & Explanation

EasyMath18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

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.

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

Approach Overview

Problem Overview: Given a range [left, right], return all numbers where every digit divides the number itself. A valid number cannot contain the digit 0, and each digit must divide the number without remainder.

Approach 1: Brute Force Digit Check (Time: O(n * d), Space: O(1))

Iterate through every number from left to right. For each number, extract digits one by one using modulo and division operations (digit = num % 10, num /= 10). If any digit is 0 or the original number is not divisible by that digit (original % digit != 0), the number is not self dividing. Otherwise continue until all digits are validated. If every digit passes the check, add the number to the result list.

This approach works because digit extraction is constant time per digit and requires no extra data structures. The complexity depends on how many digits each number has, which is d ≈ log10(n). It fits naturally into problems involving math and simple digit manipulation.

Approach 2: Digit Analysis and Skip Non-Divisible (Time: O(n * d), Space: O(1))

This approach still scans the range sequentially but optimizes the digit validation process. While extracting digits, immediately stop processing the number when encountering 0 or a digit that does not divide the number. Early termination avoids unnecessary digit checks for invalid numbers.

Some implementations also skip forward when a 0 digit appears, since any number containing 0 cannot be self dividing. This reduces redundant checks across the range. The algorithm still performs digit extraction using modulo operations but minimizes work for numbers that fail early.

The method relies purely on arithmetic operations, making it efficient and memory-friendly. It frequently appears in beginner-friendly problems involving math and number theory patterns where digits of a number influence its validity.

Recommended for interviews: Interviewers typically expect the digit-check approach with early termination. The brute force version demonstrates that you understand how to iterate through a numeric range and extract digits. The optimized digit analysis shows awareness of pruning unnecessary checks, which keeps the implementation clean and efficient while maintaining O(n * d) time and O(1) space.

Approach 1: Brute Force Approach

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Digit Analysis and Skip Non-Divisible

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Simulation

We define a function check(x) to determine whether x is a self-dividing number. The implementation idea of the function is as follows:

We use y to record the value of x, and then continuously divide y by 10 until y is 0. During this process, we check whether the last digit of y is 0, or whether x cannot be divided by the last digit of y. If either of these conditions is met, then x is not a self-dividing number, and we return false. Otherwise, after traversing all the digits, we return true.

Finally, we traverse all the numbers in the interval [left, right], and for each number, we call check(x). If it returns true, we add this number to the answer array.

The time complexity is O(n times log_{10} M), where n is the number of elements in the interval [left, right], and M = right, which is the maximum value in the interval.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

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.

Digit Analysis and Skip Non-Divisible

Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers.
Space Complexity: O(1).

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Digit CheckO(n * d)O(1)Simple implementation when checking each number independently
Digit Analysis with Early BreakO(n * d)O(1)Preferred approach in interviews due to early pruning of invalid numbers

Video Solution

LeetCode Self Dividing Numbers Solution Explained - Java • Nick White • 9,794 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Self Dividing Numbers easy or hard?
Self Dividing Numbers is classified as an Easy problem. The main challenge is correctly extracting digits and handling edge cases such as the digit 0, which automatically invalidates the number.
Self Dividing Numbers Python/Java solution
The core logic is identical across languages. Loop from left to right, extract digits using modulo, and check if each digit divides the original number. Python, Java, C++, C#, and JavaScript implementations all follow the same O(n * d) algorithm.
How to solve Self Dividing Numbers in O(n)?
Practically the solution runs in O(n * d) because each number requires digit extraction. However, since d is small (at most 10 digits for typical integer ranges), it behaves close to linear time. The optimized method stops checking digits early when encountering 0 or a non-divisible digit.
What is the best approach for Self Dividing Numbers?
The best approach is digit analysis with early termination. Iterate through the range and extract digits using modulo operations. If a digit is 0 or the number is not divisible by that digit, stop immediately. This keeps the solution simple with O(n * d) time and O(1) space complexity.
Is Self Dividing Numbers asked at Google/Amazon/Meta?
Self Dividing Numbers is generally considered a beginner-level screening problem. It appears in coding assessments and early interview rounds to evaluate basic math reasoning, loops, and digit manipulation rather than advanced algorithms.
What data structure is used in Self Dividing Numbers?
No complex data structures are required. The solution relies on arithmetic operations such as modulo and integer division to extract digits. A simple list or array is used to store the valid self dividing numbers in the result.
What is the time complexity of Self Dividing Numbers?
The time complexity is O(n * d), where n is the size of the range and d is the number of digits in each number (approximately log10(n)). Each number is processed once, and its digits are checked individually using modulo and division operations.

Ready to solve this problem?

Practice Self Dividing Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Number Has Equal Digit Count and Digit Value

Next

Count the Digits That Divide a Number