You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
Example 1:
Input: n = 12, k = 3 Output: 3 Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2 Output: 7 Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4 Output: -1 Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Constraints:
1 <= k <= n <= 1000
Follow up:
Could you solve this problem in less than O(n) complexity?
Problem Overview: Given two integers n and k, return the kth smallest factor of n. A factor is any number that divides n exactly. If n has fewer than k factors, return -1.
Approach 1: Simple Factor Collection (O(n) time, O(n) space)
The most direct solution iterates from 1 to n and checks whether each number divides n. Every time i satisfies n % i == 0, store it in a list of factors. Since iteration happens in ascending order, the list is naturally sorted. After the loop, return the element at index k - 1 if it exists. This approach uses basic iteration and arithmetic checks from math. Time complexity is O(n) because every integer up to n is checked, and space complexity is O(n) in the worst case if many factors are stored.
This method is straightforward and easy to implement. It works well when n is small or when clarity is more important than performance. The drawback is unnecessary work, since most numbers greater than sqrt(n) cannot introduce new factor pairs.
Approach 2: Optimized Factor Collection Using Divisors (O(sqrt(n)) time, O(sqrt(n)) space)
A more efficient method uses the divisor pair property: if i divides n, then n / i is also a factor. Instead of scanning the entire range up to n, iterate only from 1 to sqrt(n). For each valid divisor i, add i to one list and track the paired divisor n / i separately. This relies on core ideas from number theory.
After finishing the loop, you have two ordered groups: small factors and large paired factors. Combine them carefully so the final sequence remains sorted. Then check whether the kth element exists. Because the loop only runs up to sqrt(n), the time complexity becomes O(sqrt(n)), and the space complexity is O(sqrt(n)).
This approach significantly reduces unnecessary checks, especially when n is large. The key insight is recognizing factor symmetry around sqrt(n). It demonstrates practical understanding of divisor enumeration and efficient iteration.
Recommended for interviews: Start by explaining the linear scan approach to show you understand the definition of factors. Then move to the divisor-pair optimization using the sqrt(n) boundary. Interviewers typically expect the O(sqrt(n)) solution because it applies classic divisor enumeration from math and avoids unnecessary iteration.
The simple approach is to iterate over all numbers from 1 to n and check if a number is a factor of n by verifying if n % i == 0. We collect these factors in an array and then return the kth element if it exists. This approach ensures we capture all factors, but it has a time complexity of O(n).
The code iterates from 1 through n, checking if n is divisible by i (if i is a factor of n). It keeps a count of how many factors have been found, and if the count equals k, it returns the current factor. If no kth factor is found by the end of the loop, -1 is returned.
Time Complexity: O(n)
Space Complexity: O(1)
In this optimized approach, we iterate only up to the square root of n. For each factor i found, both i and n/i can potentially be factors. We store these in a list, ensuring no duplicates. Factors are stored in a sorted order by checking where n/i falls in relation to i.
This code iterates only up to the square root of n, storing each factor and its complement. It avoids duplicate storage when i equals n/i. After gathering all factors, it manually sorts them before returning the kth smallest factor.
Time Complexity: O(√n + k*k)
Space Complexity: O(n) due to factor storage and naive sorting.
A "factor" is a number that can divide another number. Therefore, we only need to enumerate from 1 to n, find all numbers that can divide n, and then return the k-th one.
The time complexity is O(n), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
We can observe that if n has a factor x, then n must also have a factor n/x.
Therefore, we first need to enumerate [1,2,...\left \lfloor \sqrt{n} \right \rfloor], find all numbers that can divide n. If we find the k-th factor, then we can return it directly. If we do not find the k-th factor, then we need to enumerate [\left \lfloor \sqrt{n} \right \rfloor ,..1] in reverse order, and find the k-th factor.
The time complexity is O(\sqrt{n}), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simple Factor Collection | Time Complexity: O(n) |
| Optimized Factor Collection Using Divisors | Time Complexity: O(√n + k*k) |
| Brute Force Enumeration | — |
| Optimized Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Factor Collection | O(n) | O(n) | When n is small or when implementing the most straightforward logic |
| Optimized Divisor Enumeration (sqrt method) | O(sqrt(n)) | O(sqrt(n)) | Preferred for large n and typical interview scenarios |
The kth Factor of n | the kth factor of n | leetcode 1492 | maths | 2 solutions • Naresh Gupta • 5,782 views views
Watch 9 more video solutions →Practice The kth Factor of n with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor