## Table of Contents

## Open Table of Contents

## Problem

Given two positive integers `n`

and `k`

, find the `k`

th factor of `n`

in ascending order. A factor of an integer `n`

is defined as an integer `i`

where `n % i == 0`

. Return the `k`

th 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:

**Iterate Through Numbers:**Iterate from`1`

to`n`

, checking if each number is a factor of`n`

.**Count Factors:**Maintain a count of factors. If a factor is found, increment the count.**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:

**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.**Count and Store Factors:**Maintain a count and a list of factors found. For each factor`i`

, also consider`n / i`

as a factor.**Determine kth Factor:**If`k`

is within the range of factors found, return the`k`

th 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.: This is the current factor we are checking.`i`

: This is the corresponding factor. When you divide`n // i`

`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.

- If they are the same (e.g.,

**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`

.