We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The kth Factor of n

Difficulty: Medium

Problem Description

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.

Key Insights

  • A factor of n can be found by checking integers from 1 to n.
  • The factors will be collected in a list and sorted in ascending order.
  • If the number of factors found is less than k, return -1.
  • The problem can be solved in O(n) time complexity, but optimizations can reduce it.

Space and Time Complexity

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

Solution

To find the kth factor of n, we iterate through all integers from 1 to n, checking if each integer is a factor of n (i.e., n % i == 0). We maintain a list of factors. Once we reach k factors, we can return the kth factor. If we finish checking all integers and find that there are fewer than k factors, we return -1.

Code Solutions

def kthFactor(n, k):
    factors = []
    for i in range(1, n + 1):
        if n % i == 0:
            factors.append(i)  # Add the factor to the list
        if len(factors) == k:  # If we have found k factors
            return factors[-1]  # Return the kth factor
    return -1  # Return -1 if less than k factors are found
← Back to All Questions