The kth Factor of n solution and explanation
Google
TCS
9 more videos on this problem
The kth Factor of n | the kth factor of n | leetcode 1492 | maths | 2 solutionsNaresh Gupta · 5:50 · 5K views
The kth Factor of n | Live Coding with Explanation | Leetcode #1492Algorithms Made Easy · 3:25 · 3K views
1492. The kth Factor of n | Day 019 | Math | Number Theory | Factors | DivisorsAryan Mittal · 13:01 · 1K views
LC: 1492 | The kth Factor of nShrayansh Jain · 6:29 · 1K views
The kth Factor of n | Leetcode 1492 | leetcode solutionEasyLeetcode · 6:33 · 1K views
The Kth factor of N| Leetcode 1492 | Live Coding session |Leetcode December ChallengeCoding Decoded · 7:38 · 1K views
LeetCode 1492. The kth Factor of n - Day 4 of December LeetCoding Challenge - GoMaster Coding IntervGoMaster Coding Interviews · 8:40 · 794 views
Daily Leetcode #248: Dec 04, 2020 - 1492. The kth Factor of nProgramming Live with Larry · 4:44 · 670 views
The kth Factor of n | Leetcode | SolutionAmitesh kumar · 2:13 · 621 views
1492. The kth Factor of n (Leetcode Medium)Programming Live with Larry · 2:33 · 393 views
The problem
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?
Approach overview
Problem Overview: Given two integers n and k, return the kth smallest factor of n. A factor is any number that divides n exactly. If n has fewer than k factors, return -1.
Approach 1: Simple Factor Collection (O(n) time, O(n) space)
The most direct solution iterates from 1 to n and checks whether each number divides n. Every time i satisfies n % i == 0, store it in a list of factors. Since iteration happens in ascending order, the list is naturally sorted. After the loop, return the element at index k - 1 if it exists. This approach uses basic iteration and arithmetic checks from math. Time complexity is O(n) because every integer up to n is checked, and space complexity is O(n) in the worst case if many factors are stored.
This method is straightforward and easy to implement. It works well when n is small or when clarity is more important than performance. The drawback is unnecessary work, since most numbers greater than sqrt(n) cannot introduce new factor pairs.
Approach 2: Optimized Factor Collection Using Divisors (O(sqrt(n)) time, O(sqrt(n)) space)
A more efficient method uses the divisor pair property: if i divides n, then n / i is also a factor. Instead of scanning the entire range up to n, iterate only from 1 to sqrt(n). For each valid divisor i, add i to one list and track the paired divisor n / i separately. This relies on core ideas from number theory.
After finishing the loop, you have two ordered groups: small factors and large paired factors. Combine them carefully so the final sequence remains sorted. Then check whether the kth element exists. Because the loop only runs up to sqrt(n), the time complexity becomes O(sqrt(n)), and the space complexity is O(sqrt(n)).
This approach significantly reduces unnecessary checks, especially when n is large. The key insight is recognizing factor symmetry around sqrt(n). It demonstrates practical understanding of divisor enumeration and efficient iteration.
Recommended for interviews: Start by explaining the linear scan approach to show you understand the definition of factors. Then move to the divisor-pair optimization using the sqrt(n) boundary. Interviewers typically expect the O(sqrt(n)) solution because it applies classic divisor enumeration from math and avoids unnecessary iteration.
Approach 1: Simple Factor Collection
The simple approach is to iterate over all numbers from 1 to n and check if a number is a factor of n by verifying if n % i == 0. We collect these factors in an array and then return the kth element if it exists. This approach ensures we capture all factors, but it has a time complexity of O(n).
def kth_factor(n, k):
count = 0
for i in range(1, n + 1):
if n % i == 0:
count += 1
if count == k:
return i
return -1
print(kth_factor(12, 3))public 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;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.kthFactor(12, 3));
}
}#include <iostream>
using namespace std;
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;
}
int main() {
int n = 12, k = 3;
cout << kthFactor(n, k) << endl;
return 0;
}function kthFactor(n, k) {
let count = 0;
for (let i = 1; i <= n; i++) {
if (n % i === 0) {
count++;
if (count === k) {
return i;
}
}
}
return -1;
}
console.log(kthFactor(12, 3));#include <stdio.h>
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;
}
int main() {
int n = 12, k = 3;
printf("%d\n", kthFactor(n, k));
return 0;
}using System;
public 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;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.KthFactor(12, 3));
}
}This Python function uses a loop from 1 to n to check if a number divides n without a remainder. It counts these numbers, and when the kth is found, it is returned. If not found, it returns -1.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Optimized Factor Collection Using Divisors
In this optimized approach, we iterate only up to the square root of n. For each factor i found, both i and n/i can potentially be factors. We store these in a list, ensuring no duplicates. Factors are stored in a sorted order by checking where n/i falls in relation to i.
def kth_factor(n, k):
factors = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
factors.append(i)
if i != n // i:
factors.append(n // i)
factors.sort()
if k > len(factors):
return -1
return factors[k - 1]
print(kth_factor(12, 3))import java.util.*;
public class Solution {
public int kthFactor(int n, int k) {
List<Integer> factors = new ArrayList<>();
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
factors.add(i);
if (i != n / i) factors.add(n / i);
}
}
Collections.sort(factors);
if (k > factors.size()) return -1;
return factors.get(k - 1);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.kthFactor(12, 3));
}
}#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int kthFactor(int n, int k) {
vector<int> factors;
for (int i = 1; i <= sqrt(n); ++i) {
if (n % i == 0) {
factors.push_back(i);
if (i != n / i) factors.push_back(n / i);
}
}
sort(factors.begin(), factors.end());
if (k > factors.size()) return -1;
return factors[k - 1];
}
int main() {
int n = 12, k = 3;
cout << kthFactor(n, k) << endl;
return 0;
}function kthFactor(n, k) {
const factors = [];
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
factors.push(i);
if (i !== n / i) factors.push(n / i);
}
}
factors.sort((a, b) => a - b);
return k > factors.length ? -1 : factors[k - 1];
}
console.log(kthFactor(12, 3));#include <stdio.h>
#include <math.h>
int kthFactor(int n, int k) {
int factors[1000], count = 0, sqrt_n = sqrt(n);
for (int i = 1; i <= sqrt_n; ++i) {
if (n % i == 0) {
factors[count++] = i;
if (i != n / i) factors[count++] = n / i;
}
}
if (k > count) return -1;
for (int i = 0; i < k - 1; ++i) {
for (int j = i + 1; j < count; ++j) {
if (factors[i] > factors[j]) {
int temp = factors[i];
factors[i] = factors[j];
factors[j] = temp;
}
}
}
return factors[k - 1];
}
int main() {
int n = 12, k = 3;
printf("%d\n", kthFactor(n, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int KthFactor(int n, int k) {
List<int> factors = new List<int>();
for (int i = 1; i <= Math.Sqrt(n); i++) {
if (n % i == 0) {
factors.Add(i);
if (i != n / i) factors.Add(n / i);
}
}
factors.Sort();
if (k > factors.Count) return -1;
return factors[k - 1];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.KthFactor(12, 3));
}
}In Python, we gather factors by iterating up to the square root of n, adding both the divisor and its complement to a list. We utilize Python's list sorting to find the kth factor efficiently, returning -1 if unavailable.
Time Complexity: O(√n log √n) due to the sorting of factors.
Space Complexity: O(√n).
Approach 3: Brute Force Enumeration
A "factor" is a number that can divide another number. Therefore, we only need to enumerate from 1 to n, find all numbers that can divide n, and then return the k-th one.
The time complexity is O(n), and the space complexity is O(1).
function kthFactor(n: number, k: number): number {
for (let i = 1; i <= n; ++i) {
if (n % i === 0 && --k === 0) {
return i;
}
}
return -1;
}func kthFactor(n int, k int) int {
for i := 1; i <= n; i++ {
if n%i == 0 {
k--
if k == 0 {
return i
}
}
}
return -1
}Approach 4: Optimized Enumeration
We can observe that if n has a factor x, then n must also have a factor n/x.
Therefore, we first need to enumerate [1,2,...\left \lfloor \sqrt{n} \right \rfloor], find all numbers that can divide n. If we find the k-th factor, then we can return it directly. If we do not find the k-th factor, then we need to enumerate [\left \lfloor \sqrt{n} \right \rfloor ,..1] in reverse order, and find the k-th factor.
The time complexity is O(\sqrt{n}), and the space complexity is O(1).
function kthFactor(n: number, k: number): number {
let i: number = 1;
for (; i < n / i; ++i) {
if (n % i === 0 && --k === 0) {
return i;
}
}
if (i * i !== n) {
--i;
}
for (; i > 0; --i) {
if (n % Math.floor(n / i) === 0 && --k === 0) {
return Math.floor(n / i);
}
}
return -1;
}func kthFactor(n int, k int) int {
i := 1
for ; i < n/i; i++ {
if n%i == 0 {
k--
if k == 0 {
return i
}
}
}
if i*i != n {
i--
}
for ; i > 0; i-- {
if n%(n/i) == 0 {
k--
if k == 0 {
return n / i
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Factor Collection | Time Complexity: O(n) |
| Optimized Factor Collection Using Divisors | Time Complexity: O(√n log √n) due to the sorting of factors. |
| Brute Force Enumeration | – |
| Optimized Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Factor Collection | O(n) | O(n) | When n is small or when implementing the most straightforward logic |
| Optimized Divisor Enumeration (sqrt method) | O(sqrt(n)) | O(sqrt(n)) | Preferred for large n and typical interview scenarios |
Frequently asked questions
Is The kth Factor of n easy or hard?
The problem is typically rated Medium because recognizing the sqrt(n) divisor optimization requires number theory insight. The brute force O(n) approach is easy, but the optimized solution demonstrates stronger algorithmic thinking.
The kth Factor of n Python/Java solution
In Python or Java, iterate through possible divisors and collect factors. The optimized solution loops to sqrt(n), stores divisors in lists, and returns the kth element after combining them. Both languages handle the logic with basic loops and arrays.
How to solve The kth Factor of n in O(sqrt(n))?
Iterate from 1 to sqrt(n) and check if n % i == 0. Store i as a factor and track the paired divisor n / i separately. After finishing the loop, combine the small and large factors in sorted order. Return the element at index k-1 if it exists, otherwise return -1.
What is the best approach for The kth Factor of n?
The optimal approach iterates only up to sqrt(n) and uses divisor pairs. If i divides n, then n / i is also a factor. Collect smaller factors and their paired larger factors separately, then combine them in sorted order. This reduces time complexity from O(n) to O(sqrt(n)).
Is The kth Factor of n asked at Google/Amazon/Meta?
Factor and divisor enumeration problems frequently appear in coding interviews at companies like Amazon and Google. While this exact problem may vary, the sqrt(n) divisor optimization pattern is a common interview topic in math and number theory questions.
What data structure is used in The kth Factor of n?
Most implementations use simple arrays or lists to store factors discovered during iteration. Two lists are often used in the optimized approach: one for smaller divisors and one for larger paired divisors before merging them.
What is the time complexity of The kth Factor of n?
The brute force solution checks every number from 1 to n, resulting in O(n) time complexity. The optimized divisor enumeration approach runs only up to sqrt(n), giving O(sqrt(n)) time. Space complexity is O(sqrt(n)) when storing factors.