L2. Print all Divisors of a Number | Maths Playlist

A comprehensive exploration of finding all divisors of a given integer efficiently, transitioning from a naive linear scan to an optimized square-root approach.

1. Problem Statement & Objective

Given an integer n (for example, n = 36), our objective is to return all the divisors of this number.

• Definition: A divisor of n is an integer i that divides n evenly, meaning the remainder is zero (n % i == 0).
• Order constraint: The order in which the divisors are returned does not matter, as long as all unique divisors are included.

For n = 36, the complete set of divisors includes: 1, 2, 3, 4, 6, 9, 12, 18, 36

2. Why Do We Need This? (The Naive Approach)

The most intuitive, straightforward way to find all divisors is to check every single integer from 1 up to n.

Naive Algorithm Logic

1. Start a loop from i = 1 up to n.
2. Check if n % i == 0.
3. If true, i is a divisor; store it in a list or array.

Code Implementation (Naive)

vector<int> printDivisors(int n) {
    vector<int> divisors;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
        }
    }
    return divisors;
}

Complexity Analysis of Naive Approach

• Time Complexity: $\mathcal{O}(n)$ because the loop runs exactly n times.
• Space Complexity: $\mathcal{O}(k)$ where k is the total number of divisors (used exclusively to store and return the answer).

Note: While this works perfectly for small numbers, an interviewer will expect an optimization for large values of n. Checking up to n is unnecessarily slow when mathematical properties allow us to stop much earlier.

3. Core Mental Model: Symmetrical Pairs of Divisors

To optimize our algorithm, we must observe a fundamental mathematical property of divisors: divisors always occur in pairs.

Real-Life Analogy

Mental Hook: Imagine trying to arrange 36 chairs into equal rectangular rows and columns. If you make 1 row, you need 36 columns (1 * 36 = 36). If you make 2 rows, you need 18 columns (2 * 18 = 36). If you make 3 rows, you need 12 columns (3 * 12 = 36). Notice that once you pass 6 rows * 6 columns, the combinations simply mirror themselves (e.g., 4 rows of 9 is the exact same set of chairs as 9 rows of 4). Therefore, you only need to figure out the combinations up to halfway (sqrt(n)).

Let's look at the factor pairs for 36:

• 1 $\times$ 36 = 36
• 2 $\times$ 18 = 36
• 3 $\times$ 12 = 36
• 4 $\times$ 9 = 36
• 6 $\times$ 6 = 36

Key Observations

1. If i is a divisor of n, then n / i is also a divisor of n.
   • Example: If 3 is a divisor, 36 / 3 = 12, meaning 12 is automatically a divisor.
2. One factor in every valid pair is always less than or equal to $\sqrt{n}$, and the corresponding paired factor is greater than or equal to $\sqrt{n}$.
3. Therefore, we do not need to loop all the way up to n. We only need to loop up to $\sqrt{n}$!

4. Step-by-Step Evolution: The Optimized Algorithm

By looping only up to $\sqrt{n}$, whenever we find a divisor i, we instantly capture two divisors:

1. i (found directly by the loop)
2. n / i (found via division)

Handling the Duplicate Edge Case (Perfect Squares)

When n = 36, at i = 6:

• Loop finds 6.
• Paired divisor: 36 / 6 = 6. If we blindly add both, 6 will be added twice to our list. To prevent duplicates, we must add the second divisor (n / i) only if n / i != i.

5. Avoiding Library Overhead: sqrt() vs. Multiplication

In programming languages like C++ or Java, calling library functions like sqrt() inside a loop condition can introduce unnecessary performance overhead or floating-point precision issues.

• Suboptimal Loop Condition: i <= sqrt(n) (requires math library calls on every iteration check).
• Optimal Loop Condition: i * i <= n (pure integer multiplication, highly efficient and clean).

6. Complete Optimized Code Implementation

Here is the clean, production-ready implementation incorporating the square-root boundary and duplicate check:

vector<int> printDivisorsOptimized(int n) {
    vector<int> divisors;
    
    // Loop only up to sqrt(n) using multiplication to avoid library overhead
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            // Add the first divisor from the loop
            divisors.push_back(i);
            
            // Add the paired divisor if it's different from i
            if (n / i != i) {
                divisors.push_back(n / i);
            }
        }
    }
    
    return divisors;
}

Execution Flow Walkthrough (n = 36)

7. Complexity Comparison & Synthesis

Note on Space Complexity: In both approaches, $\mathcal{O}(k)$ represents the space required to store the k divisors returned in the output array/list, which is mandated by the problem statement itself.

Summary and Key Takeaways

• Divisor Definition: A number i is a divisor of n if n % i == 0 leaves zero remainder.
• Symmetrical Pair Rule: Divisors always exist in multiplication pairs (e.g., i and n / i).
• Square Root Bound: We only need to iterate from 1 up to $\sqrt{n}$ to discover all divisor pairs, drastically reducing time complexity.
• Time Complexity Reduction: Optimized approach executes in $\mathcal{O}(\sqrt{n})$ time instead of $\mathcal{O}(n)$.
• Edge Case Prevention: For perfect squares (like 6 * 6 = 36), ensure the paired divisor is not added twice by checking n / i != i.
• Performance Best Practice: Prefer writing loop conditions as i * i <= n rather than calling library functions like i <= sqrt(n) to avoid unnecessary function call overhead.
• Order Insensitivity: The optimized approach returns divisors out of sorted order (e.g., 1, 36, 2, 18...), which is acceptable since the problem statement specifies order does not matter.