Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
1492. The kth Factor of n
Difficulty: Medium Language: JavaScript
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
Solution:
My first thought was to get a list of all factors and store them in a new array; then find out if kth factor exists. The solution below didn't need to new array, which improved space complexity from O(n) to O(1).
var kthFactor = function(n, k) {
for(let i = 1; i <= n; i++) {
//Iterating (note 1) every positive integer between 1 and n.
if((n % i) === 0) {
//for every factor found (a factor is found when remainder is 0)
//(note 2 & 3).
k--
//reduce the value of k
}
if(k === 0) return i
//if k is 0, then this is the target factor we are looking for
}
return -1
//otherwise return -1
};
Time Complexity: O(n)
Space Complexity: O(1)
References:
LeetCode Problem Link
LeetCode Discussion: Jeanstaquet
Note 1: for loop
Note 2: remainder%
Note 3: strict equality (===)
Blog Cover Image Credit
Top comments (0)