The kth Factor of n

The core idea in The kth Factor of n is that valid factors appear in ascending order, but they also come in complementary pairs around sqrt(n). A simple scan from 1 to n works because the constraints are small, yet the cleaner number theory angle is to scan up to sqrt(n), count small divisors first, then map back to their paired large divisors. That avoids extra work while preserving sorted order.

Problem Statement

You are given two positive integers n and k, and you need to look at the integers that divide n with no remainder. After listing every factor of n in increasing order, return the value at position k using 1-based indexing. If there are fewer than k total factors, return -1 instead.

For example, when n = 12, the ordered factors are 1, 2, 3, 4, 6, and 12, so the 3rd factor is 3. This problem is not about generating arbitrary divisors in any order; the real requirement is preserving ascending order, which is where factor-pair handling and perfect-square edge cases matter.

Examples

Example 1

Input: n = 12, k = 3

Output: 3

Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2

Input: n = 7, k = 2

Output: 7

Factors list is [1, 7], the 2nd factor is 7.

Example 3

Input: n = 4, k = 4

Output: -1

Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Constraints

• 1 <= k <= n <= 1000

Solution Approach

Brute-force scan from 1 to n

Because every factor must lie in the range [1, n], the most direct solution is to iterate i from 1 through n, check whether n % i == 0, and decrement k whenever you find a factor. The moment k reaches 0, return i. This is easy to implement and perfectly acceptable for n <= 1000, but it does unnecessary work after sqrt(n) because most divisors are discovered as pairs.

Use factor pairs up to sqrt(n)

A stronger Math plus Number Theory approach is to scan only up to floor(sqrt(n)). Whenever i divides n, you discover two factors: i and n / i. The smaller factor belongs earlier in sorted order, while the larger factor belongs later. Store the small divisors in order, store the paired large divisors separately, and skip duplicating sqrt(n) when n is a perfect square. This keeps the factor list correctly sorted without scanning all the way to n.

Count first, then select the kth factor

Another clean way to think about this problem is selection instead of full enumeration. First count how many small divisors you encounter up to sqrt(n). If k falls inside that small-divisor sequence, return directly from it. Otherwise, translate k into the mirrored position inside the large paired divisors. The main trade-off is indexing complexity: this version is faster conceptually, but off-by-one errors appear easily when n is a perfect square or when k lands exactly at the boundary between small and large factors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The straight scan runs in O(n) time and O(1) space because it checks every candidate from 1 to n. The factor-pair approach runs in O(sqrt(n)) time; it uses O(sqrt(n)) extra space if you store one side of the divisor pairs, or O(1) extra space if you only count and recompute carefully. For this problem, the real optimization is not asymptotic survival under huge input, but reducing wasted checks while still returning the kth factor in ascending order.

What Interviewers Usually Probe

• The interviewer mentions factors are always between 1 and n, which points to a bounded divisor scan rather than anything probabilistic or recursive.
• If they ask whether you can do better than checking all numbers up to n, they want the sqrt(n) factor-pair observation.
• If they stress sorted order, they are testing whether you notice that finding divisor pairs is easy, but returning the kth smallest factor needs careful ordering.

Common Pitfalls or Variants

Common pitfalls

• Double-counting sqrt(n) when n is a perfect square, which shifts the kth position and returns the wrong factor.
• Collecting factor pairs but forgetting that large paired divisors appear in reverse order, which breaks the required ascending list.
• Using zero-based thinking for k and returning one factor too early or too late after decrementing.

Follow-up variants

• Return the full sorted list of factors instead of only the kth one, which makes the factor-pair merge step explicit.
• Return the kth largest factor, which uses the same divisor logic but flips how you index the paired divisors.
• Handle many queries for different k on the same n, where precomputing the sorted factors once becomes more useful than repeated scans.

FAQ

What is the fastest practical way to solve The kth Factor of n?

For this problem, the cleanest practical solution is to scan up to sqrt(n) and use factor pairs. It cuts unnecessary checks and still lets you return the kth smallest factor in sorted order if you handle the large divisors carefully.

Why does scanning only to sqrt(n) work in this number theory pattern?

If i divides n, then n / i also divides n, so factors come in pairs around sqrt(n). That means every divisor larger than sqrt(n) is paired with one smaller than sqrt(n), so you do not need to test the whole range from 1 to n.

When should I just use the brute-force approach here?

Because n is at most 1000, a simple scan from 1 to n is totally acceptable and often the fastest to code correctly. In an interview, though, you should still mention the factor-pair optimization to show you understand the Math plus Number Theory pattern behind this problem.

What edge case breaks many solutions to The kth Factor of n?

Perfect squares are the main trap. When i * i == n, the pair collapses into one factor, so counting both sides would duplicate the middle divisor and corrupt the kth position.

How do I know when to return -1?

Return -1 when the total number of factors is less than k. In the brute-force version, that means you finish scanning without hitting the kth factor; in the factor-pair version, it means your combined small and large divisor count never reaches k.