All Divisors of Number - Visualization

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a positive integer n, your task is to find all of its divisors.

A divisor of a number n is any number that divides n completely (i.e., leaves no remainder).

Return the list of all such numbers in ascending order.

Examples❯

n Output Description
1 [1] 1 is the smallest positive integer; it divides itself only.
6 [1, 2, 3, 6] 6 has divisors: 1, 2, 3, and 6.
12 [1, 2, 3, 4, 6, 12] Divisors include all numbers that divide 12 with no remainder.
17 [1, 17] 17 is a prime number; only divisible by 1 and itself.
100 [1, 2, 4, 5, 10, 20, 25, 50, 100] Multiple divisors due to factors like 2, 5, and their powers.
0 [] Zero has no valid positive divisors in this context.
"" [] Empty input is treated as invalid or zero; returns empty result.

Solution❯

Understanding the Problem

We are given a positive integer n, and we need to find all of its divisors.

A divisor is any number that divides n exactly, meaning the remainder is zero.

For example, if n = 12, the numbers 1, 2, 3, 4, 6, 12 are all divisors because they divide 12 without leaving a remainder.

Our goal is to return all such numbers in ascending order.

Step-by-Step Solution with Example

Step 1: Initialize an empty list

We start by creating an empty list to collect the divisors.

Step 2: Loop from 1 to √n

Why √n? Because if i is a divisor of n, then n / i is also a divisor.

For example, for n = 12:

  • 1 divides 12 → pair is (1, 12)
  • 2 divides 12 → pair is (2, 6)
  • 3 divides 12 → pair is (3, 4)

After i = 3, any new i would result in a repeated or reversed pair.

Step 3: Check if i divides n

Inside the loop, check if n % i == 0.

If it does, add i to the list.

Also, add n / i as long as it is different from i (to avoid adding square roots twice).

Step 4: Sort the list

Since we are adding pairs in no particular order, sort the final list of divisors before returning.

Let’s go through an example: n = 12

Initialize divisors = []

Loop i from 1 to √12 (which is about 3.46, so go up to 3)

  • i = 1 → 12 % 1 == 0 → add 1 and 12
  • i = 2 → 12 % 2 == 0 → add 2 and 6
  • i = 3 → 12 % 3 == 0 → add 3 and 4

Now we have: [1, 12, 2, 6, 3, 4]

After sorting: [1, 2, 3, 4, 6, 12]

Edge Cases

  • n = 1: The only divisor is 1.
  • n is a prime number (e.g., 7): The divisors will be only 1 and n itself.
  • n is a perfect square (e.g., 36): Be careful not to add the square root twice. For example, 6 * 6 = 36, so we only add 6 once.

Final Thoughts

This method is efficient because we reduce the number of iterations from n to about √n.

It works for all positive integers and ensures correct results even when n is very large.

Sorting at the end guarantees the result is in ascending order, as required.

This approach is both beginner-friendly and optimal for number theory-related problems in competitive programming.

Algorithm Steps❯

  1. Initialize an empty list to store divisors.
  2. Iterate from 1 to sqrt(n).
  3. If i divides n (i.e., n % i == 0):
    • Add i to the list.
    • If i != n/i, also add n/i to the list.
  4. Sort the list of divisors before returning.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int cmpfunc(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x - y);
}

int main() {
    int n = 36;  // Example number
    int maxDivisors = 1000;
    int divisors[maxDivisors];
    int count = 0;
    int sqrtN = (int)sqrt(n);

    for (int i = 1; i <= sqrtN; i++) {
        if (n % i == 0) {
            divisors[count++] = i;
            if (i != n / i) {
                divisors[count++] = n / i;
            }
        }
    }

    qsort(divisors, count, sizeof(int), cmpfunc);

    printf("Divisors of %d: ", n);
    for (int i = 0; i < count; i++) {
        printf("%d ", divisors[i]);
    }
    printf("\n");
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(√n)In the best case, all divisors come in pairs (i, n/i), and the loop only runs up to √n. This ensures only √n iterations, even if n is a perfect square.
Average CaseO(√n)On average, the loop runs from 1 to √n and checks each number to see if it divides n. Each valid divisor may add up to two numbers to the list (i and n/i), but the loop count is still √n.
Worst CaseO(√n)Even if n is a large prime or perfect square, the number of iterations is limited to √n, making this approach efficient for all input sizes.

Space Complexity❯

O(√n)

Explanation: In the worst case, we could collect up to 2 × √n divisors before sorting, especially if n has many small factors. Additional space is used for the result list, which grows with the number of divisors.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...