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.

Description Hints 2 Solution Video 5:50

1492. The kth Factor of n

Medium70.8% acceptance7 companies

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 k^th 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 3^rd factor is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2^nd 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?

Asked at 7 companies

Expedia Amazon

Google Oracle

TCS Microsoft Meta

Topics

Math Number Theory

Hints open one at a time

Hint 1

The factors of n will be always in the range [1, n].

Hint 2

Keep a list of all factors sorted. Loop i from 1 to n and add i if n % i == 0. Return the kth factor if it exist in this list.

5:50

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def kthFactor(self, n: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

12
3

Input

7
2

Input

4
4

Your code is saved on this device.Solution