Get started

The kth Factor of n — Medium Problem & Solution

List the positive divisors of n in increasing order. Return the k-th of them, or -1 if n has fewer than k divisors.

  • 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 <= 1000
  • 1 <= k <= n

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

  1. Loop d from 1 to n.
  2. When n % d == 0, increment the count.
  3. Return d when the count reaches k; return -1 if 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 sqrt version, a perfect square's middle divisor must not be counted twice.
  • k can exceed the divisor count, and -1 is the required answer then — not 0.

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 -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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue