Binary Search Algorithm to Find the Smallest Divisor Given a Thr

  • Time：2020-09-11 08:23:45
  • Class：Weblog
  • Read：34

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:
Input: nums = [19], threshold = 5
Output: 4

Constraints:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6

Hints:
Examine every possible number for solution. Choose the largest of them.
Use binary search to reduce the time complexity.

Bruteforce Algorithm to Find the Smallest Divisor within a Threshold

Clearly, we can do bruteforce algorithm. The upper bound is the maximum value of the array then we can start searching the divisor from 1 to the max value. Then, at each iteration, we sum up the values using given equation s+=v/d.

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int i = 1;
        int ans = 0;
        int mv = *max_element(begin(nums), end(nums));
        while (i <= mv) {
            int s = 0;
            for (const auto &n: nums) {
                s += ceil(n * 1.0 / i);
            }
            if (s <= threshold) {
                ans = i;
                break;
            }
            i ++;
        }
        return ans;
    }
};
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int i = 1;
        int ans = 0;
        int mv = *max_element(begin(nums), end(nums));
        while (i <= mv) {
            int s = 0;
            for (const auto &n: nums) {
                s += ceil(n * 1.0 / i);
            }
            if (s <= threshold) {
                ans = i;
                break;
            }
            i ++;
        }
        return ans;
    }
};

We could use the std::accumulate to sum the array given an expression i.e. lambda expression:

1
2
3

int s = std::accumulate(begin(nums), end(nums), 0, [=](auto a, auto b) {
   return a + ceil(b * 1.0 / i);
});
int s = std::accumulate(begin(nums), end(nums), 0, [=](auto a, auto b) {
   return a + ceil(b * 1.0 / i);
});

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int i = 1;
        int ans = 0;
        int mv = Arrays.stream(nums).max().getAsInt();
        while (i <= mv) {
            int s = 0;
            for (int n: nums) {
                s += Math.ceil(n * 1.0 / i);
            }
            if (s <= threshold) {
                ans = i;
                break;
            }
            i ++;
        }
        return ans;        
    }
}
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int i = 1;
        int ans = 0;
        int mv = Arrays.stream(nums).max().getAsInt();
        while (i <= mv) {
            int s = 0;
            for (int n: nums) {
                s += Math.ceil(n * 1.0 / i);
            }
            if (s <= threshold) {
                ans = i;
                break;
            }
            i ++;
        }
        return ans;        
    }
}

Here, we use the Arrays.stream to convert an array to stream, then we can call max().getAsInt() to get the upperbound value which is the maximum value in the array.

Python (here we use the list comprehension to sum up the values):

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        i = 1
        ans = 0
        mv = max(nums)
        while i <= mv:
            s = sum([math.ceil(x / i) for x in nums])
            if s <= threshold:
                ans = i
                break
            i += 1
        return ans
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        i = 1
        ans = 0
        mv = max(nums)
        while i <= mv:
            s = sum([math.ceil(x / i) for x in nums])
            if s <= threshold:
                ans = i
                break
            i += 1
        return ans

And Javascript (using the triple dot array spreader to invoke the Math.max(…)):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let i = 1;
    let ans = 0;
    let mv = Math.max(...nums);
    while (i <= mv) {
        const s = nums.reduce((a, b) => { 
            return a + Math.ceil(b / i);
        }, 0);
        if (s <= threshold) {
            ans = i;
            break;
        }
        i ++;
    }
    return ans;       
};
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let i = 1;
    let ans = 0;
    let mv = Math.max(...nums);
    while (i <= mv) {
        const s = nums.reduce((a, b) => { 
            return a + Math.ceil(b / i);
        }, 0);
        if (s <= threshold) {
            ans = i;
            break;
        }
        i ++;
    }
    return ans;       
};

All the above implementations are O(N^2) – inefficient when N goes large.

Binary Search Algorithm to Find the Smallest Divisor Given a Threshold

Since the space is sorted: larger divisor, smaller sum. We can use the binary search algorithm that will help us find a smallest divisor in O(logN) time.

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int mv = *max_element(begin(nums), end(nums));
        int left = 1;
        int right = mv;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int s = std::accumulate(begin(nums), end(nums), 0, [=](auto a, auto b) {
                return a + ceil(b * 1.0 / mid);
            });
            if (s > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int mv = *max_element(begin(nums), end(nums));
        int left = 1;
        int right = mv;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int s = std::accumulate(begin(nums), end(nums), 0, [=](auto a, auto b) {
                return a + ceil(b * 1.0 / mid);
            });
            if (s > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

Please note that if we change the binary search boundary conditions to left <= right, then we need to change to right = mid – 1 accordingly.

The overall complexity is O(N + N.LogN) which is O(N.LogN). The O(N) is for getting the maximum value of the array, which is the upperbound – however, you could simply skip this by using a big constant value e.g. INT_MAX.

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();
        while (left < right) {
            int mid = left + (right - left) / 2;
            int s = 0;
            for (int x: nums) {
                s += Math.ceil(x * 1.0 / mid);
            }
            if (s > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();
        while (left < right) {
            int mid = left + (right - left) / 2;
            int s = 0;
            for (int x: nums) {
                s += Math.ceil(x * 1.0 / mid);
            }
            if (s > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import math
 
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left = 1
        right = max(nums)
        while left <= right:
            mid = left + (right - left) // 2
            s = sum(math.ceil(x/mid) for x in nums)
            if s > threshold:
                left = mid + 1
            else:
                right = mid - 1
        return left
import math

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left = 1
        right = max(nums)
        while left <= right:
            mid = left + (right - left) // 2
            s = sum(math.ceil(x/mid) for x in nums)
            if s > threshold:
                left = mid + 1
            else:
                right = mid - 1
        return left

And Javascript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let left = 1;
    let right = Math.max(...nums);
    while (left < right) {
        let s = 0;
        const mid = left + Math.floor((right - left) / 2);
        for (const x of nums) {
            s += Math.ceil(x / mid);
        }
        if (s > threshold) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let left = 1;
    let right = Math.max(...nums);
    while (left < right) {
        let s = 0;
        const mid = left + Math.floor((right - left) / 2);
        for (const x of nums) {
            s += Math.ceil(x / mid);
        }
        if (s > threshold) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

We can use the Array.reduce in Javascript:

1
2
3

const s = nums.reduce((a, b) => { 
   return a + Math.ceil(b / mid);
}, 0);
const s = nums.reduce((a, b) => { 
   return a + Math.ceil(b / mid);
}, 0);

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Blogging for Dummies in 2019: The Only Cheat Sheet You Need
Are Readers Reaching Your Call To Action?
How to Manage a Content Marketing Plan for Your Blog
4 Simple Techniques To Bring Your Dead Blog Back To Life
How to Earn Bitcoin Through Blogging
5 PayPal Alternatives for Bloggers and Solopreneurs
Can WordPress Make Other E-commerce Platforms Obsolete?
How to Start a Food Blog (A Step-By-Step 2019 Guide)
3 Possible Solutions to the Most Common Corporate Blogging Probl
Why Social Media is Crucial to Your Marketing Efforts
Share：Facebook Twitter
Comment list
Comment add