Smallest Divisor

JavaView on GFG

Intuition

Find smallest divisor such that sum of ceiling(arr[i]/divisor) <= threshold. Binary search.

Algorithm

1Binary search on divisor in [1, max(arr)]. For each divisor d: check if sum of ceil(arr[i]/d) <= threshold.

Common Pitfalls

•Same as LC 1283. Binary search on answer. Ceiling division: (a+b-1)/b or math.ceil. O(n log max).

Smallest Divisor.java

Java

// Approach: Binary search on divisor. Count ceiling(arr[i]/d) sum; check if <= threshold.
// Time: O(n log(max)) Space: O(1)
import java.util.*;

class Solution {
    int smallestDivisor(int[] arr, int k) {
        Arrays.sort(arr);
        int i = 1;
        int j = arr[arr.length - 1];
        int ans = 0;
        while (i <= j) {
            int mid = (i + j) >> 1;
            int divValue = check(mid, k, arr);
            if (divValue > k)
                i = mid + 1;
            else {
                ans = mid;
                j = mid - 1;
            }
        }
        return ans;
    }

    int check(int mid, int k, int[] arr) {
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            double temp = (double) arr[i] / (double) mid;
            int ftemp = (int) Math.ceil(temp);
            cnt += ftemp;
        }
        return cnt;
    }
}

Was this solution helpful?