Skip to main content
Talentd

The kth Factor of n - Solution & Explanation

MediumMathNumber Theory17 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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).

The code iterates from 1 through n, checking if n is divisible by i (if i is a factor of n). It keeps a count of how many factors have been found, and if the count equals k, it returns the current factor. If no kth factor is found by the end of the loop, -1 is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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.

This code iterates only up to the square root of n, storing each factor and its complement. It avoids duplicate storage when i equals n/i. After gathering all factors, it manually sorts them before returning the kth smallest factor.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(√n + k*k)
Space Complexity: O(n) due to factor storage and naive sorting.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simple Factor Collection

Time Complexity: O(n)
Space Complexity: O(1)

Optimized Factor Collection Using Divisors

Time Complexity: O(√n + k*k)
Space Complexity: O(n) due to factor storage and naive sorting.

Brute Force Enumeration—
Optimized Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simple Factor CollectionO(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

Video Solution

The kth Factor of n | the kth factor of n | leetcode 1492 | maths | 2 solutions • Naresh Gupta • 5,784 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice The kth Factor of n with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer