Katkat
Back

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

PDT PartnersMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

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

Input: n = 97
Output: [1, 97]

97 is prime, so its only divisors are 1 and 97.

Example 3

Input: n = 1
Output: [1]