DSA interview question

Print All Divisors of a Number

Easy · Algorithms · Topics: basic maths, number theory

The problem

A scheduling tool splits N minutes of workshop time into equal-length sessions, and the organiser wants to see every possible session length, meaning every divisor of N, in increasing order. N can be as large as 10^9, so checking every number from 1 to N would take seconds per request. The key observation is that divisors come in pairs (i, N / i), and one of each pair is always at most √N. Checking only up to √N finds all of them.

Example: N = 36 → 1 2 3 4 6 9 12 18 36.

Function signature

vector<long long> divisors(long long n);  // all divisors of n in increasing order, n >= 1

Test cases

Input `n`	Output	Explanation
36	`1 2 3 4 6 9 12 18 36`	6 × 6 = 36, so 6 appears only once
20	`1 2 4 5 10 20`	Pairs (1, 20), (2, 10), (4, 5)
1	`1`
13	`1 13`	A prime has exactly two divisors
100	`1 2 4 5 10 20 25 50 100`	Perfect square: 10 once
999999937	`1 999999937`	Largest prime below 10^9; only about 31,623 checks

(Confirm: 1 ≤ n ≤ 10^9 (or larger); output in increasing order without duplicates.)

How interviewers phrase it

"Print all divisors of N in sorted order."
"Count the number of divisors" or "find the sum of divisors of N."
Frequently a lead-in to prime checking, prime factorisation, or perfect-number problems.

Clarifying questions to ask

What's the range of N? (Decides between O(N) and O(√N).)
Must the output be sorted?
Should 1 and N themselves be included?
How many queries? (Many queries might call for a sieve-based approach.)

Follow-ups to expect

"Why is it enough to check up to √N?"
"How do you keep the output sorted without sorting?"
"How do you avoid the duplicate for perfect squares?"
"Why write i <= n / i instead of i * i <= n?"
"How would you count divisors for many numbers up to 10^6?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview