1842. Divisor Ladder
A tile maker wants every row length that divides a floor of n tiles into equal rows with none left over. Given the positive integer n, return every positive divisor of n in ascending order. For example, the divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36.
Checking every number up to n is too slow when n is large. Divisors come in pairs i and n / i, so it is enough to test values of i up to the square root of n. Take care not to list a divisor twice when i equals n / i. Aim for O(sqrt n) time.
Example 1
- Input:
- n = 36
- Output:
- [1,2,3,4,6,9,12,18,36]
- Explanation:
The pairs are (1, 36), (2, 18), (3, 12), (4, 9) and 6 on its own.
Example 2
- Input:
- n = 13
- Output:
- [1,13]
- Explanation:
A prime has only 1 and itself.
Example 3
- Input:
- n = 1
- Output:
- [1]
- Explanation:
1 has one divisor.
Constraints
1 ≤ n ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt n)
- Space
- O(d)