Problem Description

You are given two integers n and k. The task is to find the kth smallest factor of n. A factor of n is defined as a number i such that when n is divided by i, there is no remainder, i.e., n % i == 0. The factors are considered in ascending order. If n does not have k factors, the function should return -1.

Intuition

The intuition behind the solution is to find all the factors of the given integer n, sort them in increasing order and then return the kth one in the sequence. Since the factors of a number are symmetric around the square root of the number, the solution starts by iterating through all numbers from 1 to the square root of n. For each number i that is a factor of n (meaning n % i == 0), it decrements k because it is one step closer to the kth smallest factor.

If k reaches 0 during this process, it returns the current factor, i. However, if k is still not 0 after this loop ends, the solution then uses a slightly different approach. It checks the symmetric factors by dividing n by i and continues decreasing k until it finds the kth factor or until there are no more factors to check. Again, if k reaches 0 during this process, it returns the current factor, n // i.

One important case to handle is when n is a perfect square. In such a case, the factor that is exactly the square root of n is only counted once, hence the second loop begins by decrementing i by 1, to avoid double-counting.

The solution efficiently finds the kth smallest factor by avoiding the generation of all factors, instead, all the while counting the position of each factor it finds until it reaches the kth one.

Learn more about Math patterns.

Solution Approach

The implementation of the solution involves a straightforward iteration through possible factors and can be broken down into two main stages:

1. Finding Factors Less Than or Equal to Square Root:

   • Initialize i to 1.
   • Loop until i squared is less than n:
     • Check if i is a factor using the modulus operation n % i == 0. If it is, decrement k.
     • If k reaches 0 within this loop, return i because you've found the kth factor.
     • Increment i to check the next potential factor.

2. Finding Factors Greater Than Square Root:

   • Before starting this loop, check if n is a perfect square by verifying if the square of i-1 (last i from previous loop) is not equal to n; if it isn't, we reduce i by 1 to ensure we do not repeat the factor at the square root of n in case n is a perfect square.
   • Loop downwards from i:
     • Check for the other factor by dividing n by i and see if the modulo with n // i is 0 ((n % (n // i)) == 0).
     • As before, with each successful factor, decrement k.
     • If k reaches 0 within this loop, return the corresponding factor n // i because you've found the kth factor.
     • Decrement i and continue until i reaches 0.

3. Returning -1:

   • In case the total number of factors is less than k, return -1.

This approach uses no additional data structures, relying only on integer variables to track the current candidate factor and the countdown of k to reach the desired factor. It is efficient because it minimizes the number of iterations to potentially a little more than twice the square root of n. The algorithm capitalizes on the symmetry of factors and avoids a full enumeration of factors beyond the 'middle' factor (the square root), thus optimizing the search for the kth factor.

Example Walkthrough

Let's illustrate the solution approach with an example. Say we are given the integers n = 12 and k = 3. Our goal is to find the 3rd smallest factor of 12.

According to the problem, the factors of 12 are 1, 2, 3, 4, 6, and 12. The 3rd smallest factor in this list is 3.

Step 1 - Finding Factors Less Than or Equal to Square Root:

• We start by initializing i to 1. Since 12 is not a perfect square, we will iterate up to its square root. The square root of 12 is approximately 3.46, so we'll consider all numbers up to 3.
• For i = 1, we check if it's a factor of 12 (12 % 1 == 0). It is, so we decrement k to 2.
• For i = 2, we check if it's a factor (12 % 2 == 0). It is, so we decrement k to 1.
• For i = 3, we check if it's a factor (12 % 3 == 0). It is, and since k is now 1, decrementing it will bring it to 0. We have found the 3rd smallest factor, so we can return i which is 3.

Since we found the kth smallest factor before exhausting all factors up to the square root of n, there is no need to proceed to Step 2.

If k had been greater, such as 5, the steps would continue as follows:

Step 2 - Finding Factors Greater Than Square Root:

• As n = 12 is not a perfect square, we continue to look for factors greater than the square root. We had last checked i = 3, so we start with i = 4.
• We decrement i to 3 and loop downwards:
  • Check i = 3: Since we've already counted this factor in the first loop, we don't count it again.
  • Check i = 2: We find 12 // 2 = 6 is a factor (12 % 6 == 0). We decrement k to 0. We've found the 5th smallest factor, so we return n // i which is 6.

Step 3 - Returning -1:

• This step is not necessary for our example as we've found our kth factor. If k were larger than the number of factors 12 has, this step would ensure that we return -1 to indicate that there is no kth factor. For instance, if k = 8, after checking all possible factors, k would not be 0, so we would return -1.

The solution approach has successfully found the 3rd smallest factor of 12 in a few simple steps. It’s efficient and effective for any pair of n and k provided.

Solution Implementation

Time and Space Complexity

The time complexity of the given code can be assessed by examining the two while loops that are run in sequence to find the k-th factor of the integer n.

The first loop runs while i * i < n, which means it will run approximately sqrt(n) times, because it stops when i is just less than the square root of n. Within this loop, the operation performed is a modulo operation to check if i is a factor of n, which is an O(1) operation. Therefore, the time complexity contributed by the first loop is O(sqrt(n)).

The second loop starts with i set to a value slightly less than sqrt(n) (assuming n is not a perfect square) and counts down to 1. For each iteration, it performs a modulo operation, which is O(1). However, not every i will lead to an iteration because the counter is reduced only when (n % (n // i)) == 0, which corresponds to the outer factors of n. Since there are as many factors less than sqrt(n) as there are greater than sqrt(n), we can expect the second loop also to contribute a time complexity of O(sqrt(n)).

Combining both loops, the overall time complexity remains O(sqrt(n)), as they do not compound on each other but are sequential.

The space complexity of the code is O(1) as there are only a finite number of variables used (i, k, n), and no additional space is allocated that would grow with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.