1492. The kth Factor of n
Problem Description
You are given two integers n
and k
. The task is to find the k
th 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 k
th 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 k
th 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 k
th 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 k
th 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 k
th 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:
-
Finding Factors Less Than or Equal to Square Root:
- Initialize
i
to 1. - Loop until
i
squared is less thann
:- Check if
i
is a factor using the modulus operationn % i == 0
. If it is, decrementk
. - If
k
reaches 0 within this loop, returni
because you've found thek
th factor. - Increment
i
to check the next potential factor.
- Check if
- Initialize
-
Finding Factors Greater Than Square Root:
- Before starting this loop, check if
n
is a perfect square by verifying if the square ofi-1
(lasti
from previous loop) is not equal ton
; if it isn't, we reducei
by 1 to ensure we do not repeat the factor at the square root ofn
in casen
is a perfect square. - Loop downwards from
i
:- Check for the other factor by dividing
n
byi
and see if the modulo withn // 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 factorn // i
because you've found thek
th factor. - Decrement
i
and continue untili
reaches 0.
- Check for the other factor by dividing
- Before starting this loop, check if
-
Returning -1:
- In case the total number of factors is less than
k
, return-1
.
- In case the total number of factors is less than
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 k
th factor.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 decrementk
to 2. - For
i = 2
, we check if it's a factor (12 % 2 == 0
). It is, so we decrementk
to 1. - For
i = 3
, we check if it's a factor (12 % 3 == 0
). It is, and sincek
is now 1, decrementing it will bring it to 0. We have found the 3rd smallest factor, so we can returni
which is 3.
Since we found the k
th 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 checkedi = 3
, so we start withi = 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 decrementk
to 0. We've found the 5th smallest factor, so we returnn // i
which is 6.
- Check
Step 3 - Returning -1:
- This step is not necessary for our example as we've found our
k
th factor. Ifk
were larger than the number of factors 12 has, this step would ensure that we return-1
to indicate that there is nok
th factor. For instance, ifk = 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
1class Solution:
2 def kthFactor(self, n: int, k: int) -> int:
3 # Initialize a variable to count factors
4 factor_count = 0
5 # Iterate over potential factors from 1 up to the square root of n
6 for potential_factor in range(1, int(n**0.5) + 1):
7 # If the potential_factor is a factor of n
8 if n % potential_factor == 0:
9 # Increment the count of factors found
10 factor_count += 1
11 # If this is the k-th factor, return it
12 if factor_count == k:
13 return potential_factor
14
15 # If the loop completes, there are two possibilities:
16 # Either k is too large (more than the number of factors), or
17 # the k-th factor is the complement factor of a factor before the square root of n
18 # To handle this, start decrementing potential_factor and check if its complement is a factor
19 # If n is a perfect square, we need to avoid counting the square root twice
20 if int(n**0.5)**2 == n:
21 potential_factor = int(n**0.5) - 1
22 else:
23 potential_factor = int(n**0.5)
24
25 # Iterate over remaining potential factors from the square root of n to 1
26 for i in range(potential_factor, 0, -1):
27 # Check if i is a factor by seeing if the division of n by i has no remainder
28 if n % i == 0:
29 # Decrease k as we are counting down from the total number of factors
30 factor_count += 1
31 # If this is the k-th factor, return its complement factor
32 if factor_count == k:
33 return n // i
34
35 # If no k-th factor was found, return -1
36 return -1
37
1class Solution {
2 // Method to find the k-th factor of a number n
3 public int kthFactor(int n, int k) {
4 // Starting from 1, trying to find factors in increasing order
5 int factor = 1;
6 for (; factor <= n / factor; ++factor) {
7 // If 'factor' is a factor of 'n' and it's the k-th one found
8 if (n % factor == 0 && (--k == 0)) {
9 // Return 'factor' as the k-th factor of 'n'
10 return factor;
11 }
12 }
13 // Adjust 'factor' if we've surpassed the square root of 'n'
14 // because we will look for factors in the opposite direction now
15 if (factor * factor != n) {
16 factor--;
17 }
18 // Starting from the last found factor, searching in decreasing order
19 for (; factor > 0; --factor) {
20 // Calculate the corresponding factor pair
21 if (n % (n / factor) == 0) {
22 // Decrease k for each factor found
23 k--;
24 // If we found the k-th factor from the largest end
25 if (k == 0) {
26 // Return the factor as it's the k-th factor of 'n'
27 return n / factor;
28 }
29 }
30 }
31 // If no k-th factor is found, return -1
32 return -1;
33 }
34}
35
1class Solution {
2public:
3 int kthFactor(int n, int k) {
4 // Initialize the factor candidate
5 int factor = 1;
6
7 // Loop through potential factors starting from 1
8 for (; factor < n / factor; ++factor) {
9 // Check if current factor divides n without remainder
10 if (n % factor == 0) {
11 // Decrease k for each factor found
12 --k;
13 // If k reaches 0, the current factor is the kth factor
14 if (k == 0) {
15 return factor;
16 }
17 }
18 }
19
20 // If the loop exited normally, check for a perfect square
21 if (factor * factor == n) {
22 // If n is a perfect square, we do not double count it
23 --factor;
24 }
25
26 // Iterate backwards from the potential largest factor
27 for (; factor > 0; --factor) {
28 // Find the corresponding factor pair
29 int correspondingFactor = n / factor;
30 // Check if it divides n without remainder
31 if (n % correspondingFactor == 0) {
32 // Decrease k for each factor found
33 --k;
34 // If k reaches 0, this is the kth factor
35 if (k == 0) {
36 return correspondingFactor;
37 }
38 }
39 }
40
41 // If kth factor does not exist, return -1
42 return -1;
43 }
44};
45
1// Function to find the kth factor of n
2function kthFactor(n: number, k: number): number {
3 // Initialize the factor candidate
4 let factor = 1;
5
6 // Loop through potential factors starting from 1
7 while (factor < n / factor) {
8 // Check if the current factor divides n without remainder
9 if (n % factor === 0) {
10 // Decrease k for each factor found
11 k--;
12
13 // If k reaches 0, the current factor is the kth factor
14 if (k === 0) {
15 return factor;
16 }
17 }
18 factor++;
19 }
20
21 // If the loop exited normally, check for a perfect square
22 if (factor * factor === n) {
23 // If n is a perfect square, we do not double count it
24 factor--;
25 }
26
27 // Iterate backwards from the potential largest factor
28 while (factor > 0) {
29 // Find the corresponding factor pair
30 let correspondingFactor = n / factor;
31
32 // Check if it divides n without remainder
33 if (n % correspondingFactor === 0) {
34 // Decrease k for each factor found
35 k--;
36
37 // If k reaches 0, this is the kth factor
38 if (k === 0) {
39 return correspondingFactor;
40 }
41 }
42 factor--;
43 }
44
45 // If the kth factor does not exist, return -1
46 return -1;
47}
48
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.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first