Need to Change Constraints and Add Follow up - 1492. The kth Factor of n

[stormsunshine]

Your LeetCode username

stormsunshine

Category of the bug

• [x] Question
• [ ] Solution
• [ ] Language
• [x] Missing Test Cases

Description of the bug

For 1492. The kth Factor of n, the maximum values of both k and n are too small and a solution with time complexity O(n) can get accepted.

However, this problem has an optimized solution with time complexity O(√n) (√n means the square root of n), which is more likely to be expected during an interview. Since this problem is designed to accepted an O(n) solution, the values of n and k should still make the O(n) solution pass, but the values should be changed to larger values to distinguish between O(n) time complexity and O(√n) time complexity.

Therefore, the following two points can be enhanced.

1. Change the constraints to 1 <= k <= n <= 10⁶ or 1 <= k <= n <= 10⁷. Although the maximum value of n is changed to a larger value, the O(n) solution should still get accepted without getting TLE.
2. After changing the constraints, add one or more test cases with larger values of k and n. The cases where the kth factor is less than or equal to √n, the kth factor is greater than √n, and the kth factor is -1 should all be included in new test cases.
3. Add a follow up: Can you solve this problem with time complexity less than O(n)?

Code you used for Submit/Run operation

The following code has time complexity O(n).

class Solution {
    public int kthFactor(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;
    }
}

The following code has time complexity O(√n).

class Solution {
    public int kthFactor(int n, int k) {
        if (k == 1)
            return 1;
        int count = 0, factor = 1;
        while (factor * factor <= n) {
            if (n % factor == 0) {
                count++;
                if (count == k)
                    return factor;
            }
            factor++;
        }
        factor--;
        if (factor * factor == n)
            factor--;
        while (factor > 0) {
            if (n % factor == 0) {
                count++;
                if (count == k)
                    return n / factor;
            }
            factor--;
        }
        return -1;
    }
}

Language used for code

Java

Expected behavior

1. Change the constraints to 1 <= k <= n <= 10⁶ or 1 <= k <= n <= 10⁷. Although the maximum value of n is changed to a larger value, the O(n) solution should still get accepted without getting TLE.
2. After changing the constraints, add one or more test cases with larger values of k and n. The cases where the kth factor is less than or equal to √n, the kth factor is greater than √n, and the kth factor is -1 should all be included in new test cases.
3. Add a follow up: Can you solve this problem with time complexity less than O(n)?

[LC-Sue]

Hi @stormsunshine Thank you for reaching out to us. I've relayed this issue to our team to investigate.

[LC-Sue]

Hi @stormsunshine, Thank you for your time, our team has reviewed your report and decided to keep the constraints as is. We appreciate your support!