The kth Factor of n — Solution in Python, Java & C++
The kth Factor of n solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
The kth Factor of n is a medium coding problem on math and number theory, asked in Amazon, Adobe and TCS interviews.
- Difficulty: Medium
- Topics: Math, Number Theory
- Asked at: Amazon, Adobe, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
List the positive divisors of n in increasing order.
Return the k-th of them, or -1 if n has fewer than k divisors.
Example 1
Input: n = 12, k = 3
Output: 3
Explanation: The divisors are 1, 2, 3, 4, 6, 12.
Example 2
Input: n = 7, k = 2
Output: 7
Explanation: A prime has exactly two divisors.
Example 3
Input: n = 4, k = 4
Output: -1
Explanation: 4 has only three divisors.
Constraints
1 <= n <= 10001 <= k <= n
Hints for The kth Factor of n
Hint 1
A direct loop from
1toncounting divisors is fine at this size.Hint 2
The
O(sqrt(n))version collects the small divisors going up and the large ones coming back down.Hint 3
Stop as soon as the running count reaches
k.
How to solve The kth Factor of n
Divisors are naturally enumerated in increasing order by a loop from 1 upward, so count as you go and stop at the k-th.
Approach
- Loop
dfrom1ton. - When
n % d == 0, increment the count. - Return
dwhen the count reachesk; return-1if the loop ends first.
Why it works
The loop visits candidates in increasing order, so the k-th divisor it finds is exactly the k-th smallest. The O(sqrt(n)) refinement uses the pairing d ↔ n/d: collect the d <= sqrt(n) ascending, then walk the partners descending.
Complexity
- Time —
O(n), or O(sqrt(n)) with the pairing trick - Space —
O(1)
Pitfalls
- In the
sqrtversion, a perfect square's middle divisor must not be counted twice. kcan exceed the divisor count, and-1is the required answer then — not0.
Reference solution
Python
def kthFactor(n: int, k: int) -> int:
seen = 0
for d in range(1, n + 1):
if n % d == 0:
seen += 1
if seen == k:
return d
return -1Java
public static int kthFactor(int n, int k) {
int seen = 0;
for (int d = 1; d <= n; d++) {
if (n % d == 0) {
seen++;
if (seen == k) return d;
}
}
return -1;
}C++
int kthFactor(int n, int k) {
int seen = 0;
for (int d = 1; d <= n; d++) {
if (n % d == 0) {
seen++;
if (seen == k) return d;
}
}
return -1;
}JavaScript
var kthFactor = function(n, k) {
var seen = 0;
for (var d = 1; d <= n; d++) {
if (n % d === 0) {
seen++;
if (seen === k) return d;
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.