PPractick

The problem

A party-planning app splits n guests into equal-sized tables and wants to show every possible table size, meaning all divisors of n in increasing order. Checking every number up to n is O(n), too slow for n near 10⁹. Divisors come in pairs (i, n / i) with i ≤ √n, so scanning i up to √n finds them all. Collect the small halves in order and the large halves in reverse, and take care not to list √n twice for perfect squares.

Example: 20 → 1 2 4 5 10 20.

Function signature

vector<long long> divisors(long long n);  // ascending; n >= 1

Test cases

Input	Output	Explanation
20	1 2 4 5 10 20	Pairs (1, 20), (2, 10), (4, 5)
21191	1 21191	A prime
36	1 2 3 4 6 9 12 18 36	6 · 6 is listed once
1	1
12	1 2 3 4 6 12

(Confirm: n ≥ 1; each divisor appears once, in increasing order.)

How interviewers phrase it

• "Given an integer N, print all its divisors in ascending order" (GeeksforGeeks "All divisors of a Number").

Clarifying questions to ask

1. Should 1 and n be included? (Yes.)
2. Must the output be sorted?
3. How large is n? (Up to about 10⁹, which means O(√n).)

Follow-ups to expect

1. "Why stop at √n?"
2. "How do you keep the output sorted without sorting?"
3. "Perfect squares?"
4. "How many divisors can a number have?"
5. "Complexity?"

Related questions

• Print Prime Factors of a Number Hard
• Count primes in range L to R Hard
• Prime factorisation of a Number Hard
• Count all Digits of a Number Easy
• Reverse a number Easy
• Palindrome Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in