Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

All divisors of a Number

EASYProblemSolveExternal Links

Description

Given a positive integer n, find all distinct divisors of n and return them in ascending order.

A divisor (or factor) of n is a positive integer that divides n with zero remainder. For example, the divisors of 20 are 1, 2, 4, 5, 10, and 20 because each of these numbers divides 20 exactly.

Every positive integer n has at least two divisors: 1 and n itself (except when n = 1, which has only one divisor).

Examples

Example 1

Input: n = 20

Output: [1, 2, 4, 5, 10, 20]

Explanation: Check which numbers from 1 to 20 divide 20 evenly:

  • 20 ÷ 1 = 20 ✓
  • 20 ÷ 2 = 10 ✓
  • 20 ÷ 3 = 6.67 ✗
  • 20 ÷ 4 = 5 ✓
  • 20 ÷ 5 = 4 ✓
  • 20 ÷ 10 = 2 ✓
  • 20 ÷ 20 = 1 ✓

The 6 divisors of 20 in ascending order are [1, 2, 4, 5, 10, 20].

Example 2

Input: n = 21191

Output: [1, 21191]

Explanation: 21191 is a prime number — it has no divisors other than 1 and itself. So the answer is [1, 21191].

Example 3

Input: n = 36

Output: [1, 2, 3, 4, 6, 9, 12, 18, 36]

Explanation: 36 is a perfect square (6×6). Its divisor pairs are: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Since 6×6 = 36, we include 6 only once. Total 9 divisors.

Constraints

  • 1 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to find all divisors of n is to check every number from 1 to n. For each candidate i, if n is divisible by i (i.e., n % i == 0), then i is a divisor of n.

Think of it like a toll booth test: you line up every number from 1 to n and ask each one, "Do you divide n evenly?" Anyone who passes the test gets added to the result list.

This guarantees we find every divisor and they come out in ascending order naturally (since we iterate from 1 upward).

Step-by-Step Explanation

Let's trace through with n = 20:

Step 1: Initialize empty result list. Start checking from i = 1.

Step 2: i = 1. Is 20 % 1 == 0? Yes → add 1 to result. Result = [1].

Step 3: i = 2. Is 20 % 2 == 0? Yes → add 2. Result = [1, 2].

Step 4: i = 3. Is 20 % 3 == 0? No (20 % 3 = 2). Skip.

Step 5: i = 4. Is 20 % 4 == 0? Yes → add 4. Result = [1, 2, 4].

Step 6: i = 5. Is 20 % 5 == 0? Yes → add 5. Result = [1, 2, 4, 5].

Step 7: i = 6 through 9. None divide 20 evenly. Skip all.

Step 8: i = 10. Is 20 % 10 == 0? Yes → add 10. Result = [1, 2, 4, 5, 10].

Step 9: i = 11 through 19. None divide 20 evenly. Skip all.

Step 10: i = 20. Is 20 % 20 == 0? Yes → add 20. Result = [1, 2, 4, 5, 10, 20].

Step 11: i > 20, stop. Return [1, 2, 4, 5, 10, 20].

Algorithm

  1. Initialize an empty list divisors
  2. Iterate i from 1 to n:
    a. If n % i == 0, append i to divisors
  3. Return divisors

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> allDivisors(int n) {
        vector<int> divisors;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                divisors.push_back(i);
            }
        }
        return divisors;
    }
};
class Solution:
    def allDivisors(self, n):
        divisors = []
        for i in range(1, n + 1):
            if n % i == 0:
                divisors.append(i)
        return divisors
import java.util.*;

class Solution {
    public List<Integer> allDivisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
            }
        }
        return divisors;
    }
}

Complexity Analysis

Time Complexity: O(n)

We check every integer from 1 to n, performing one modulo operation per check. With n up to 10^9, this means up to one billion iterations — which would take several seconds and likely exceed time limits.

Space Complexity: O(1)

Excluding the output list, we use only a loop variable. The output list itself stores at most O(√n) divisors (a known upper bound on the number of divisors of n), but we don't count output in space analysis.

Why This Approach Is Not Efficient

The brute force checks all n candidates, but the vast majority fail the divisibility test. For n = 10^9, we make a billion modulo operations, yet n has at most ~1344 divisors (the maximum divisor count for any number up to 10^9). That means 99.99998% of our checks are wasted.

The key insight: divisors come in pairs. If i is a divisor of n, then n/i is also a divisor of n. For example, with n = 20:

  • 1 × 20 = 20 → both 1 and 20 are divisors
  • 2 × 10 = 20 → both 2 and 10 are divisors
  • 4 × 5 = 20 → both 4 and 5 are divisors

In every pair (i, n/i), the smaller one satisfies i ≤ √n and the larger one satisfies n/i ≥ √n. So we only need to iterate up to √n — for each divisor we find below the square root, we automatically get its paired divisor above the square root for free.

For n = 10^9, √n ≈ 31,623 — that's 31,000× fewer iterations than the brute force.

Optimal Approach - Divisor Pairs up to √n

Intuition

Every divisor of n belongs to a pair (i, n/i) where i × (n/i) = n. In any such pair, at least one element is ≤ √n and the other is ≥ √n.

Proof: If both i and n/i were greater than √n, then i × (n/i) > √n × √n = n, contradicting i × (n/i) = n. So at least one must be ≤ √n.

This means we can find ALL divisors by only checking candidates from 1 to √n:

  • When i divides n, add i to the result
  • Also add the paired divisor n/i to the result (if it's different from i)

The only edge case is when n is a perfect square — then i = √n and n/i = √n are the same number, so we must add it only once to avoid duplicates.

Since we collect divisors from both ends (small ones directly, large ones as pairs), the result won't be sorted. We need to sort it at the end — or use a two-list technique where we collect small divisors in ascending order and large divisors in descending order, then concatenate them.

Step-by-Step Explanation

Let's trace through with n = 36 (a perfect square — the interesting case).

√36 = 6, so we iterate i from 1 to 6.

Step 1: Initialize two lists: small = [] (divisors ≤ √n), large = [] (divisors > √n). We will iterate i from 1 to √36 = 6.

Step 2: i = 1. Is 36 % 1 == 0? Yes. Add 1 to small. Pair = 36/1 = 36 ≠ 1, so add 36 to large. small = [1], large = [36].

Step 3: i = 2. Is 36 % 2 == 0? Yes. Add 2 to small. Pair = 36/2 = 18 ≠ 2, so add 18 to large. small = [1, 2], large = [36, 18].

Step 4: i = 3. Is 36 % 3 == 0? Yes. Add 3 to small. Pair = 36/3 = 12 ≠ 3, so add 12 to large. small = [1, 2, 3], large = [36, 18, 12].

Step 5: i = 4. Is 36 % 4 == 0? Yes. Add 4 to small. Pair = 36/4 = 9 ≠ 4, so add 9 to large. small = [1, 2, 3, 4], large = [36, 18, 12, 9].

Step 6: i = 5. Is 36 % 5 == 0? No (36 % 5 = 1). Skip. First "miss" — not every candidate is a divisor.

Step 7: i = 6. Is 36 % 6 == 0? Yes. Add 6 to small. Pair = 36/6 = 6. Since 6 == 6 (perfect square case!), do NOT add to large. small = [1, 2, 3, 4, 6], large = [36, 18, 12, 9].

Step 8: Reverse large to get ascending order: [9, 12, 18, 36]. Concatenate small + reversed large: [1, 2, 3, 4, 6] + [9, 12, 18, 36] = [1, 2, 3, 4, 6, 9, 12, 18, 36].

Step 9: Return [1, 2, 3, 4, 6, 9, 12, 18, 36]. All 9 divisors found by checking only 6 candidates instead of 36.

Divisor Pairs up to √n — Finding All Divisors of 36 — Watch how iterating only up to √36 = 6 discovers all 9 divisors by exploiting the pairing property. The primary array builds small divisors (≤√n), while the secondary array builds large divisors (>√n).

Algorithm

  1. Initialize two lists: small for divisors ≤ √n, large for divisors > √n
  2. Iterate i from 1 to √n (inclusive):
    a. If n % i == 0:
    • Add i to small
    • If i ≠ n/i (not a perfect square pair), add n/i to large
  3. Reverse large to convert it from descending to ascending order
  4. Concatenate small + reversed large
  5. Return the concatenated result

Code

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> allDivisors(int n) {
        vector<int> small, large;
        
        for (int i = 1; i <= (int)sqrt((double)n); i++) {
            if (n % i == 0) {
                small.push_back(i);
                if (i != n / i) {
                    large.push_back(n / i);
                }
            }
        }
        
        // Reverse large to get ascending order
        reverse(large.begin(), large.end());
        
        // Concatenate small + large
        for (int x : large) {
            small.push_back(x);
        }
        return small;
    }
};
import math

class Solution:
    def allDivisors(self, n):
        small = []
        large = []
        
        for i in range(1, int(math.isqrt(n)) + 1):
            if n % i == 0:
                small.append(i)
                if i != n // i:
                    large.append(n // i)
        
        # Reverse large to get ascending order and concatenate
        return small + large[::-1]
import java.util.*;

class Solution {
    public List<Integer> allDivisors(int n) {
        List<Integer> small = new ArrayList<>();
        List<Integer> large = new ArrayList<>();
        
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                small.add(i);
                if (i != n / i) {
                    large.add(n / i);
                }
            }
        }
        
        // Reverse large to get ascending order
        Collections.reverse(large);
        
        // Concatenate
        small.addAll(large);
        return small;
    }
}

Complexity Analysis

Time Complexity: O(√n)

The loop runs from 1 to √n, performing one modulo operation per iteration. For n = 10^9, this is only about 31,623 iterations — easily within time limits. The reversal of the large list takes at most O(√n) time as well, since a number n has at most O(√n) divisors. Total: O(√n).

Space Complexity: O(1)

Excluding the output, we only use a loop variable and the two lists that collectively store the output divisors. The number of divisors of n is at most O(n^(1/3) × polylog) in the worst case but practically bounded by a small number. The auxiliary space beyond the output is O(1).

Why this is optimal: Any algorithm that finds all divisors must output each divisor at least once. The number of divisors can be up to ~1344 for n ≤ 10^9, and our loop does √n ≈ 31,623 iterations. Since we must at least check enough candidates to confirm whether each potential divisor exists, O(√n) is the best known time for this problem. No approach can beat O(√n) without factorization shortcuts that don't generalize to all n.