Solving LeetCode’s The kth Factor of n

In this article, we will be solving LeetCode’s The kth Factor of n in JavaScript. I recently did a similar problem for a technical assessment, so I wanted to dive in more into this kind of problem. I found this problem very interesting especially in finding ways to make the runtime quicker. A factor is a number that divides another number completely without leaving any remainder.

Problem

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

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Solution

Explanation

The key part of this problem is to collect every factorial for n. Something we know is that whatever n value can always be factored by 1 and n. 1 will always be the smallest factor and n the largest factor of n. One quick check that we have at the very start is if k = 1. If it does, then we do not have to search for all the factors, the factor of any n at k = 1 will always be 1. For that same reason, we create our factors array to have 1 already in it. We can start our for loop at i = 2 and we only want to go until i is equal to n/2. That is because if 2 is a factor of n, then the second largest factor will be n/2. It is unnecessary to iterate all the way to n. All the rest of the factors will be less than n/2. If i is a factor of n, we add it to our factors array. After the for loop, we push n into our array because n is the largest factor of n. We check if the kth factor exists in our factors array, if it does return the kth factor. If not, we return -1.

Big O

Time complexity — O(n)

Space complexity — O(n)

Resources

LeetCode Problem: https://leetcode.com/problems/the-kth-factor-of-n/