Binary Search Algorithm to Find the Smallest Divisor Given a Thr

  • 时间：2020-09-11 08:23:45
  • 分类：网络文摘
  • 阅读：79 次

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) —

推荐阅读：
The Beginners’ Guide to Trie: How to Use the Trie in C++?　 5 Ways To Revamp Your 40 Hour Work Week　 Pros & Cons of Using a New TLD for Your Blog　 Facebook Apologizes After Deleting Blogger’s Post “By Accident”　 Want to Differentiate Your Content? Aim for Interaction　 Top Tech Trends To Watch For In 2016　 7 ABC’s for Turning Words into Money with Your Blog　 Here’s What You Don’t Know About The Oxford Comma　 Euro 2016: Underway And Plenty Has Changed　 A Look Behind the Curtain of the Fashion Blogging World　
评论列表
添加评论