LeetCode 1283: Find the Smallest Divisor Given a Threshold Solution

Master LeetCode problem 1283 (Find the Smallest Divisor Given a Threshold), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1283. Find the Smallest Divisor Given a Threshold

Medium

Array Binary Search

Problem Explanation

Explanation

To solve this problem, we can use binary search to find the smallest divisor that meets the given threshold. We first set the search space as [1, max(nums)], where max(nums) is the maximum value in the input array. Then we perform binary search within this search space. For each iteration of binary search, we calculate the sum of divisions using the current divisor and check if it is less than or equal to the threshold. If it is, we update the result and continue searching for a smaller divisor. If it is not, we narrow down the search space by adjusting the binary search boundaries.

Time complexity: O(n * log(max(nums))), where n is the number of elements in the input array and max(nums) is the maximum value in the array. Space complexity: O(1)

Solution Code

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1, right = Arrays.stream(nums).max().getAsInt();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = calculateSum(nums, mid);
            
            if (sum <= threshold) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private int calculateSum(int[] nums, int divisor) {
        int sum = 0;
        for (int num : nums) {
            sum += (int) Math.ceil((double) num / divisor);
        }
        return sum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1283 (Find the Smallest Divisor Given a Threshold)?

This page provides optimized solutions for LeetCode problem 1283 (Find the Smallest Divisor Given a Threshold) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1283 (Find the Smallest Divisor Given a Threshold)?

The time complexity for LeetCode 1283 (Find the Smallest Divisor Given a Threshold) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1283 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1283 in Java, C++, or Python.

Back to LeetCode Solutions