The kth Factor of n

Medium
708.

The kth Factor of n

The kth Factor of n is a medium coding problem on math and number theory, asked in Amazon, Adobe and TCS interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthFactor = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for The kth Factor of n

  1. Hint 1

    A direct loop from 1 to n counting divisors is fine at this size.

  2. Hint 2

    The O(sqrt(n)) version collects the small divisors going up and the large ones coming back down.

  3. 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

  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

Java

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.

All 337 math problems · the whole catalogue