The kth Factor of n – C++ Solution

Problem Description

So, you think you can find the kth factor of a number n? Well, welcome to the club! The problem is simple: given a number n, you need to find its kth factor. But wait, it’s not as easy as it sounds! Imagine you’re at a party, and you’re trying to find the kth person who can do the Macarena dance. You might have to sift through a lot of people before you find that one special dancer. Similarly, in this problem, you’ll have to sift through the factors of n to find the kth one.

Code Solution

Here’s the code that will help you find that elusive kth factor:

Copy Code

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

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

• Time Complexity: O(√n) – The algorithm only checks up to the square root of n for factors, making it efficient.
• Space Complexity: O(1) – The solution uses a constant amount of space, regardless of the input size.

Real-World Example

Imagine you’re at a buffet, and you want to find the kth dish that you can eat without feeling guilty. You start checking each dish, and if you find a dish that fits your criteria, you count it. If you reach the kth dish, you can finally indulge! This is similar to how the algorithm checks each factor of n until it finds the kth one.