LeetCode 1492 - The kth Factor of n

Table of Contents

Problem

Given two positive integers n and k, find the kth factor of n in ascending order. A factor of an integer n is defined as an integer i where n % i == 0. 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.

Constraints:

• 1 <= k <= n <= 1000

Follow up: Could you solve this problem in less than O(n) complexity?

Approaches

Brute Force Approach:

1. Iterate Through Numbers: Iterate from 1 to n, checking if each number is a factor of n.
2. Count Factors: Maintain a count of factors. If a factor is found, increment the count.
3. Check kth Factor: When the count reaches k, return the current number. If k is greater than the number of factors, return -1.

Optimized Approach:

1. Iterate with Early Stopping: Iterate from 1 to the square root of n. This is because factors beyond the square root of n are complements of the factors before it.
2. Count and Store Factors: Maintain a count and a list of factors found. For each factor i, also consider n / i as a factor.
3. Determine kth Factor: If k is within the range of factors found, return the kth factor. Otherwise, return -1.

Code Implementation

Brute Force

def kthFactor(n, k):
    count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            count += 1
            if count == k:
                return i
    return -1

Optimized

def kthFactor(n, k):
    # Initialize an empty list to store the factors of n
    factors = []

    # Iterate through numbers from 1 to the square root of n (inclusive)
    for i in range(1, int(n**0.5) + 1):
        # Check if i is a factor of n
        if n % i == 0:
            # If i is a factor, add it to the list of factors
            factors.append(i)
            # Check if the corresponding factor (n // i) is different from i
            if i != n // i:
                # If it is different, add the corresponding factor to the list
                factors.append(n // i)

    # Sort the list of factors in ascending order
    factors.sort()

    # Check if the list of factors is long enough to have a k-th element
    if k <= len(factors):
        # If it is, return the k-th factor (considering 1-based indexing)
        return factors[k - 1]

    # If the k-th factor does not exist, return -1
    return -1

Brute Force:

• Time Complexity: O(n), as we potentially iterate through all numbers from 1 to n.
• Space Complexity: O(1), since no additional space is used besides variables for iteration and counting.

Optimized:

• Time Complexity: O(√n), as the loop runs up to the square root of n, and sorting takes O(factors log factors) time, where factors is typically much smaller than n.
• Space Complexity: O(√n), to store the factors of n.

Visual Explanation

Step 1: Initialize Factors List

• We start with an empty list to store factors.

factors = []

Step 2: Iterate to Find Factors

• We iterate from 1 to √30 (approximately 5.47), hence up to 5.

Step 3: Check and Add Factors

• For each iteration, we check if i is a factor of 30.

Iteration 1: i = 1

• 1 is a factor of 30, add 1.
• Corresponding factor: 30 // 1 = 30. Since 30 is not 1, add 30.

factors = [1, 30]

Iteration 2: i = 2

• 2 is a factor of 30, add 2.
• Corresponding factor: 30 // 2 = 15. Since 15 is not 2, add 15.

factors = [1, 30, 2, 15]

Iteration 3: i = 3

• 3 is a factor of 30, add 3.
• Corresponding factor: 30 // 3 = 10. Since 10 is not 3, add 10.

factors = [1, 30, 2, 15, 3, 10]

Iteration 4: i = 4

• 4 is not a factor of 30. Skip.

Iteration 5: i = 5

• 5 is a factor of 30, add 5.
• Corresponding factor: 30 // 5 = 6. Since 6 is not 5, add 6.

factors = [1, 30, 2, 15, 3, 10, 5, 6]

Step 4: Sort the Factors

• Sort the factors list.

factors = [1, 2, 3, 5, 6, 10, 15, 30]

Step 5: Select the k-th Factor

• k = 4, so we select the 4th element from the sorted list.

4th factor = factors[3] = 5

• The 4th smallest factor of 30 is 5.

In-detail explanation of Optimized Solution

The function is designed to find all factors of a given number n. A factor is a number that divides n without leaving a remainder. For every factor i found, there could potentially be a corresponding factor, which is n // i.

The Line if i != n // i:

• Purpose: To avoid duplicates in the list of factors.
• Scenario: When finding factors of n, some numbers might be squared factors. For example, if n = 36, one of the factors is 6, and 36 // 6 is also 6. We don’t want to add 6 twice to our list of factors.
• i: This is the current factor we are checking.
• n // i: This is the corresponding factor. When you divide n by i, you get another factor of n.

Detailed Explanation

• When the function iterates through possible factors, i, it also considers n // i as a potential factor.
• The line if i != n // i: checks if these two factors are actually the same number.
  • If they are the same (e.g., i = 6 and n // i = 6 for n = 36), we don’t need to add n // i to our factors list because i is already added.
  • If they are different (e.g., i = 2 and n // i = 18 for n = 36), both are valid unique factors and should be included in the list.

Example

Let’s take n = 12 as an example:

• For i = 2: n // i is 12 // 2 which equals 6. Here, 2 and 6 are different, so both are added.
• For i = 3: n // i is 12 // 3 which equals 4. Here, 3 and 4 are different, so both are added.
• If n were 16, for i = 4, n // i is 16 // 4 which equals 4. Here, 4 and 4 are the same, so we only add 4 once.

The line if i != n // i: ensures that each factor is only added once to the list, even in cases where n is a perfect square or when two factors are numerically equal. This is crucial for correctly counting and listing distinct factors of n.