Find the Smallest Divisor Given a Threshold
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Find the smallest positive integer divisor such that dividing each array element by it (using ceiling division) yields a sum <= threshold, Arrays, Loops, Time Complexity, Space Complexity, Brute Force, Binary Search, Mathematical Algorithms, Conditional Statements, complexity analysis, brute force, mathematical operations, search space optimization, binary search, Mathematical Operations, Search Space.
You are given an array of integers arr and an integer limit. Your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division's result is less than or equal to the given threshold value. While dividing the array elements with a chosen number, we will always take the ceiling value. For example, ceil(3 / 2) = 2. Input: An array of integers arr. An integer limit. Output: The smallest positive integer divisor that satisfies the condition. Examples: Example 1: Example 2: