Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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.
Example 1:
Input: n = 12, k = 3 Output: 3 Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2 Output: 7 Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4 Output: -1 Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Constraints:
1 <= k <= n <= 1000Follow up:
Could you solve this problem in less than O(n) complexity?
Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
12 3
7 2
4 4
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1492: The kth Factor of n
class Solution {
public int kthFactor(int n, int k) {
for (int i = 1; i <= n; ++i) {
if (n % i == 0 && (--k == 0)) {
return i;
}
}
return -1;
}
}
// Accepted solution for LeetCode #1492: The kth Factor of n
func kthFactor(n int, k int) int {
for i := 1; i <= n; i++ {
if n%i == 0 {
k--
if k == 0 {
return i
}
}
}
return -1
}
# Accepted solution for LeetCode #1492: The kth Factor of n
class Solution:
def kthFactor(self, n: int, k: int) -> int:
for i in range(1, n + 1):
if n % i == 0:
k -= 1
if k == 0:
return i
return -1
// Accepted solution for LeetCode #1492: The kth Factor of n
struct Solution;
impl Solution {
fn kth_factor(n: i32, mut k: i32) -> i32 {
for i in 1..=n {
if n % i == 0 {
k -= 1;
if k == 0 {
return i;
}
}
}
-1
}
}
#[test]
fn test() {
let n = 12;
let k = 3;
let res = 3;
assert_eq!(Solution::kth_factor(n, k), res);
let n = 7;
let k = 2;
let res = 7;
assert_eq!(Solution::kth_factor(n, k), res);
let n = 4;
let k = 4;
let res = -1;
assert_eq!(Solution::kth_factor(n, k), res);
let n = 1;
let k = 1;
let res = 1;
assert_eq!(Solution::kth_factor(n, k), res);
let n = 1000;
let k = 3;
let res = 4;
assert_eq!(Solution::kth_factor(n, k), res);
}
// Accepted solution for LeetCode #1492: The kth Factor of n
function kthFactor(n: number, k: number): number {
for (let i = 1; i <= n; ++i) {
if (n % i === 0 && --k === 0) {
return i;
}
}
return -1;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.