The kth Factor of n

Ah, the classic problem of finding the kth factor of a number. It’s like trying to find the right slice of pizza in a box full of toppings you didn’t order. You know it’s there, but good luck figuring out which one it is! In this problem, you’re tasked with finding the kth factor of a given integer n. So, if you’ve ever felt overwhelmed by choices (like deciding between pineapple or pepperoni), this problem is for you!

Problem Description

Imagine you’re at a party, and you’re trying to figure out how many people can fit in a car. Each person represents a factor of the number of seats in the car (let’s say n). You want to know who the kth person is that can squeeze in. If you can’t find that person, well, it’s back to the drawing board—or in this case, back to the math!

In more technical terms, given an integer n, you need to return the kth factor of n. If n has fewer than k factors, return -1.

Solution Links

Language Options
C++ Solution
Python Solution

Code Solution


class Solution {
  public int kthFactor(int n, int k) {
    int factor = 1;
    int i = 0; // the i-th factor

    for (; factor * factor < n; ++factor)
      if (n % factor == 0 && ++i == k)
        return factor;

    for (factor = n / factor; factor >= 1; --factor)
      if (n % factor == 0 && ++i == k)
        return n / factor;

    return -1;
  }
}

Approach Explanation

The approach taken in this code is quite clever. It first finds all the factors of n by iterating through numbers up to the square root of n. If a number is a factor, it checks if it’s the kth factor. If not, it continues to find the corresponding factor from the other side (n divided by the factor). This way, it efficiently finds the kth factor without having to check every single number up to n.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(√n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re organizing a game night with your friends, and you have 12 chairs (n = 12). You want to know who the 3rd person to sit down is (k = 3). The factors of 12 are 1, 2, 3, 4, 6, and 12. So, the 3rd factor is 3. If you had only 5 chairs, and you were looking for the 6th person, well, sorry buddy, you’d have to wait for someone to leave!