Scale Engineer

The kth Factor of n

Med
#1377Time: O(n). In the worst-case scenario, we might have to iterate through all numbers from 1 to `n` to find the k-th factor or to determine that it doesn't exist.Space: O(1). We only use a few variables to store the counter and the loop index, regardless of the size of `n`.2 companies
Patterns
MathNumber Theory
Companies
ExpediaIBM

Prompt

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?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward linear scan through all numbers from 1 to n. For each number, we check if it's a factor of n. We use a counter to keep track of how many factors we've found. When the counter reaches k, we've found our target and can return the current number.

Algorithm

  • Initialize a counter count to 0.
  • Iterate with a loop variable i from 1 to n.
  • Inside the loop, check if i is a factor of n using the modulo operator (n % i == 0).
  • If i is a factor, increment count.
  • If count becomes equal to k, it means i is the k-th factor. Return i immediately.
  • If the loop completes without the count reaching k, it implies that n has fewer than k factors. In this case, return -1.

Walkthrough

The brute-force algorithm is the most intuitive way to solve this problem. We simply iterate through all possible candidates for factors, which are the integers from 1 up to n.

We maintain a counter, initialized to zero. As we iterate, if we find a number i that divides n evenly (n % i == 0), we've found a factor. Since we are iterating in ascending order, the first factor we find is the 1st factor, the second is the 2nd, and so on. We increment our counter for each factor found. As soon as our counter equals k, we have located the k-th factor and can return it. If we iterate through all numbers up to n and the counter never reaches k, it means n has fewer than k factors, and we should return -1 as per the problem description.

class Solution {    public int kthFactor(int n, int k) {        int count = 0;        for (int i = 1; i <= n; ++i) {            if (n % i == 0) {                count++;                if (count == k) {                    return i;                }            }        }        return -1;    }}

Complexity

Time

O(n). In the worst-case scenario, we might have to iterate through all numbers from 1 to `n` to find the k-th factor or to determine that it doesn't exist.

Space

O(1). We only use a few variables to store the counter and the loop index, regardless of the size of `n`.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Requires minimal memory (constant space complexity).

Cons

  • The time complexity is linear with respect to n, which can be slow if n is very large. For the given constraints (n <= 1000), it's acceptable, but it doesn't scale well.

Solutions

class Solution {public  int kthFactor(int n, int k) {    for (int i = 1; i <= n; ++i) {      if (n % i == 0 && (--k == 0)) {        return i;      }    }    return -1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem