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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The kth Factor of n

Number: 1585

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Salesforce, IBM, Microsoft, Meta, Apple, Goldman Sachs, Expedia

Problem Description

Given two positive integers n and k, find the kth factor of n when all factors of n are listed in ascending order. If n has fewer than k factors, return -1.

Key Insights

  • Factors of n come in pairs (i and n/i), which allows iterating only up to sqrt(n) for efficiency.
  • Use two lists: one to collect smaller factors (i) and one for their corresponding larger partners (n/i).
  • Reverse the larger factor list and then merge with the smaller factor list to get a sorted order.
  • Handle perfect squares carefully to avoid adding the same factor twice.
  • For very small n (n <= 1000), this approach is very efficient, although it meets the follow-up challenge for reducing from O(n) to approximately O(sqrt(n)).

Space and Time Complexity

Time Complexity: O(√n) – looping only through numbers up to √n. Space Complexity: O(√n) – storing factors up to √n and their corresponding counterparts.

Solution

The basic idea is to iterate i from 1 to √n. If i divides n, then i is a factor and n/i is also a factor (if distinct). Append i into a "lowFactors" list and n/i into a "highFactors" list. After the loop, reverse the "highFactors" list to restore ascending order and then merge it with "lowFactors". Finally, check if the kth factor exists in the merged list; if yes, return it, otherwise, return -1.

Code Solutions

def kthFactor(n, k):
    # List to store factors found from 1 to sqrt(n)
    low_factors = []
    # List to store corresponding higher factors
    high_factors = []
    
    # Iterate from 1 up to the square root of n
    i = 1
    while i * i <= n:
        if n % i == 0:
            low_factors.append(i)  # i is a factor
            # Avoid duplicate factors for perfect squares
            if i != n // i:
                high_factors.append(n // i)
        i += 1
    
    # Combine the factors in ascending order:
    # low_factors is already sorted; reverse high_factors to get them in ascending order when appended
    factors = low_factors + high_factors[::-1]
    
    # Check if kth factor exists
    return factors[k - 1] if k <= len(factors) else -1

# Example usage:
print(kthFactor(12, 3))  # Output: 3
print(kthFactor(7, 2))   # Output: 7
print(kthFactor(4, 4))   # Output: -1
← Back to All Questions