Leetcode 1362 Closest Divisors

In this Leetcode problem, we need to return a list of two integers [m, p]such that m * p = n + 1 or m * p = n + 2 and such that |m — p| is minimal for all [m, p] satisfying the first condition.

Here is the problem statement and examples:

Problem statement and examples

Solution

The first idea is that we can first find the minimum for n + 1, then the minimum for n + 2 and then pick the minimum of the 2 values.

Then, we can notice that the minimum such pair for n + 1 is the one containing the divisor of n + 1 closest to Math.sqrt(n + 1). In a way, it is similar to finding if the number is prime, but instead we select the highest divisor closest to Math.sqrt(n + 1) . We do the same for n + 2.

public int[] findDivisors(int n) {
        int div = 1;
        for (int i = (int) Math.sqrt(n); i > 1; i--) {
            if (n % i == 0) {
                div = i;
                break;
            }
        }
        int[] res = new int[2];
        res[0] = div;
        res[1] = n / div;
        return res;
    }

Then, in the main method, we find the best pair for n + 1 and n + 2, then pick the one with the smallest difference. Here is the full code:

class Solution {
    public int[] closestDivisors(int num) {
        int[] r1 = findDivisors(num + 1);
        int[] r2 =…