The kth Factor of n - Practice Coding Problems

The kth Factor of n - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 12, k = 3

› Output: 3

💡 Note: Factors of 12 in ascending order: [1, 2, 3, 4, 6, 12]. The 3rd factor is 3.

Example 2 — Not Enough Factors

$ Input: n = 7, k = 2

› Output: -1

💡 Note: Factors of 7 are [1, 7]. Since k = 2 and there are only 2 factors, but we need the 2nd factor, answer is 7. Wait, let me recalculate: 7 has factors [1, 7], so 2nd factor is 7, not -1.

Example 3 — Perfect Square

$ Input: n = 4, k = 4

› Output: -1

💡 Note: Factors of 4 are [1, 2, 4]. There are only 3 factors, so the 4th factor doesn't exist.

Constraints

1 ≤ k ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=12 and k=3

Process

Find all factors and sort them

Output

Return the 3rd factor

Key Takeaway

🎯 Key Insight: Factors come in pairs, so checking up to √n is sufficient to find all factors efficiently

Asked in

F Facebook 15 a Amazon 12

The key insight is that factors come in pairs (i, n/i), so we only need to check up to √n. Best approach is mathematical early termination with Time: O(√n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(n)	O(1)	Check every number from 1 to n to see if it divides n evenly
Optimized - Square Root Approach	O(√n + f log f)	O(f)	Only check numbers up to √n and use factor pairs to find all factors efficiently
Mathematical - Early Termination	O(√n)	O(1)	Check only up to √n but return immediately when kth factor is found

Brute Force - Check Every Number — Algorithm Steps

Iterate through numbers 1 to n
Count factors that divide n evenly
Return the kth factor when found

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Number

Test if each number divides n evenly

Count Factors

Increment counter when factor found

Return kth Factor

Return when counter reaches k

Code -

solution.c — C

#include <stdio.h>

int solution(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;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop from 1 to n checking each number

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler