The kth Factor of n Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Cisco Expedia Twitter
MathViews 4464

Problem Statement

The kth Factor of n Leetcode Solution: states that 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:

The factor list is [1, 7], and the 2nd factor is 7.

Example 3:

Input:

n = 4, k = 4

Output:

-1

Explanation:

The factors list is [1, 2, 4], and there are only 3 factors. We should return -1.

Approach

Idea:

Suppose we are given a number n, we will run a loop from 1 to n.

For each iteration, we will check if n%i==0 i.e n is divisible by i. At the same time, we will increase the count variable.

If count equals k for certain i, then we have found the kth factor of n, and we will return i.

If no such kth factor of n is found, then return -1. In the worst case, the loop runs till n, Hence O(n) is the worst-case time complexity.

Code

The kth Factor of n Leetcode C++ Solution:

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;
   }
};

The kth Factor of n Leetcode Java Solution:

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;
    }
}

The kth Factor of n Leetcode Python Solution:

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
       count = 0
       for i in range(1, n + 1):
           if math.fmod(n, i)==0:
               count += 1
           if count == k:
               return i
       return -1

Complexity Analysis for the kth Factor of n LeetCode Solution:

Time Complexity

The time complexity of the above code is O(n). We start finding factors from 1 to n and in the worst case, it iterates till n. Hence, the worst-case time complexity is O(n).

Space Complexity

The space complexity of the above code is O(1) since we aren’t using any extra space here.

Translate »