Find All Divisors of a Number
Solve this Problem
Given a positive integer
n, return every divisor of n — every integer from 1 to n that divides it with no remainder — sorted in ascending order.
Divisors always come in pairs: if i divides n, so does n / i. That pairing means you never need to test anything past √n — for every small divisor found on the way up, its larger partner is found for free, without ever touching it directly.
Test Case 1:
Input:n = 36
Output:[1, 2, 3, 4, 6, 9, 12, 18, 36]
Explanation:36 has 9 divisors — every pair (i, 36 / i) that divides evenly, collected and sorted.
Test Case 2:
Input:n = 12
Output:[1, 2, 3, 4, 6, 12]
Explanation:12 = 2² × 3, giving (2 + 1) × (1 + 1) = 6 divisors.
Test Case 3:
Input:n = 7
Output:[1, 7]
Explanation:7 is prime, so its only divisors are 1 and itself.
Constraints
- ◆
1 ≤ n ≤ 10⁹
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Linear Scan
BruteTry every candidate from 1 to n, and keep the ones that divide n with no remainder. Correct and simple, but it walks the entire range even though most candidates past √n are just the "large" half of a pair already found on the way up.
Time
O(n)Space
O(1) extraJava
1class Solution {
2 public int[] findDivisors(int n) {
3 List<Integer> result = new ArrayList<>();
4 for (int i = 1; i <= n; i++) {
5 if (n % i == 0) {
6 result.add(i);
7 }
8 }
9 int[] arr = new int[result.size()];
10 for (int j = 0; j < arr.length; j++) {
11 arr[j] = result.get(j);
12 }
13 return arr;
14 }
15}Optimal — Divisor Pairs up to √n
OptimalDivisors always come in pairs: if i divides n, so does n / i. So it's enough to test i from 1 up to √n — collect the small half (i) going up, and the large half (n / i) going down. When i and n / i are equal (a perfect square), record it only once. Concatenating the small list with the large list reversed gives the full sorted result with no separate sort step.
Time
O(√n)Space
O(number of divisors)Java
1class Solution {
2 public int[] findDivisors(int n) {
3 List<Integer> small = new ArrayList<>();
4 List<Integer> large = new ArrayList<>();
5 for (int i = 1; (long) i * i <= n; i++) {
6 if (n % i == 0) {
7 small.add(i);
8 if (i != n / i) {
9 large.add(n / i);
10 }
11 }
12 }
13 int[] result = new int[small.size() + large.size()];
14 int idx = 0;
15 for (int x : small) result[idx++] = x;
16 for (int j = large.size() - 1; j >= 0; j--) result[idx++] = large.get(j);
17 return result;
18 }
19}