Quick Overview

Given a positive integer up to one trillion, return every positive divisor in ascending order, each listed once. The task tests divisor enumeration, correct handling of perfect squares and 64-bit values, and a follow-up asking whether the running time can grow more slowly than the square root of n.

List All Positive Divisors of an Integer in Ascending Order, Then Beat Square-Root Time

Company: PDT Partners

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a positive integer `n`, return every positive integer that divides `n` exactly, in ascending order. As a follow-up, once you have a correct solution, the interviewer asked whether the running time can grow more slowly than $\sqrt{n}$. ### Function Signature ```python def all_divisors(n: int) -> list[int]: ``` ### Rules - A positive integer `d` is a divisor of `n` when `n % d == 0`. - Return each divisor exactly once, sorted in strictly ascending order. The list always starts with `1` and ends with `n`. ### Constraints - `1 <= n <= 10^12` - `n` can exceed `2^31 - 1`, so use 64-bit integers in languages with fixed-width integer types. Every value stays well within `2^53`. ### Examples **Example 1** ```text Input: n = 36 Output: [1, 2, 3, 4, 6, 9, 12, 18, 36] ``` 36 is a perfect square (6 × 6 = 36), and the divisor 6 appears only once. **Example 2** ```text Input: n = 97 Output: [1, 97] ``` 97 is prime, so its only divisors are 1 and 97. **Example 3** ```text Input: n = 1 Output: [1] ```

Overview: Given a positive integer up to one trillion, return every positive divisor in ascending order, each listed once. The task tests divisor enumeration, correct handling of perfect squares and 64-bit values, and a follow-up asking whether the running time can grow more slowly than the square root of n.

Read the full PDT Partners Machine Learning Engineer interview experience this question came from

Given a positive integer `n`, return every positive integer that divides `n` exactly, in ascending order. A positive integer `d` is a divisor of `n` when `n % d == 0`. Return each divisor exactly once, sorted in strictly ascending order. The list always starts with `1` and ends with `n`. `n` can exceed 2^31 - 1, so use 64-bit integers in languages with fixed-width integer types (Java `long`, C++ `long long`). Every input value and every returned divisor is at most 10^12, well within 2^53. Example 1: Input: n = 36 Output: [1, 2, 3, 4, 6, 9, 12, 18, 36] Explanation: 36 is a perfect square (6 * 6 = 36), and the divisor 6 appears only once. Example 2: Input: n = 97 Output: [1, 97] Explanation: 97 is prime, so its only divisors are 1 and 97. Constraints: - 1 <= n <= 10^12 Follow-up: once you have a correct solution, can the running time grow more slowly than sqrt(n)?

Constraints

  • 1 <= n <= 10^12
  • n can exceed 2^31 - 1, so use 64-bit integers in languages with fixed-width integer types (Java long, C++ long long); every input and every returned divisor is at most 10^12, well within 2^53.

Examples

Input: (1,)

Expected Output: [1]

Explanation: Minimum valid n: 1 is its own only divisor, so the first and last element coincide and must not be duplicated.

Input: (2,)

Expected Output: [1, 2]

Explanation: Smallest prime: only 1 and n.

Hints

  1. Testing every candidate from 1 to n is far too slow when n is close to 10^12. Which candidates do you actually need to test?
  2. Example 1 points out that 36 is a perfect square and 6 appears only once. Make sure your method neither drops nor duplicates such a divisor.
  3. n can exceed 2^31 - 1, so check that your integer types and any loop-bound arithmetic cannot overflow.

Loading coding console...

Show the approach

Approach

Algorithm: divisors come in pairs (d, n / d), and in every pair the smaller member is at most sqrt(n). Compute r = floor(sqrt(n)) exactly: take the floating-point square root, then correct it with integer checks (decrease while r * r > n, increase while (r + 1) * (r + 1) <= n), so a rounding error near 10^12 cannot shift the bound. For each d from 1 to r with n % d == 0, append d to a low list and, if n / d != d, append n / d to a high list. Return low followed by high reversed.

Invariant: after processing d, low holds every divisor <= d in ascending order, and high holds their cofactors in descending order.

Correctness: any divisor e <= r is visited directly. Any divisor e > r has cofactor n / e < sqrt(n), so n / e <= r is visited, and e is added as its cofactor. Each divisor is added once, because the only case where a pair's two members coincide (d = n / d, i.e. n is a perfect square) is skipped. Every element of low is <= r, and every element of high is >= r + 1 or equals n / d > d, so low entirely precedes reversed high and the result is strictly ascending, starting with 1 and ending with n.

Edge cases: n = 1 gives r = 1 and returns [1] once; primes give [1, n]; perfect squares (36, 999983^2) list the square root once; values above 2^31 - 1 use 64-bit arithmetic (Java long, C++ long long), and r * r stays at most about 10^12, inside 2^53 for JavaScript.

Follow-up: trial-dividing to factor n and stopping once the remaining cofactor has no factor below its own square root is much faster when n has small prime factors, and the divisors can then be generated from the factorization and sorted. In the worst case (n prime, or a product of two primes near sqrt(n)) plain trial division still takes about sqrt(n) steps; going below that needs a sub-sqrt factoring method such as Pollard's rho with a Miller-Rabin primality test, which runs in about n^(1/4) expected steps. The output size is the number of divisors of n in every case.

Time complexity:
O(sqrt(n))
Space complexity:
O(d(n)), where d(n) is the number of divisors of n (the output size)