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

推荐阅读：
月饼是“三高”食品 六类人群不宜多吃　 谁来保障转基因食品的公众知情权？　 适宜老年人的秋令养阴滋补的菜肴　 营养专家建议的老年人健康饮食原则　 绑架“第一口奶”该曝光的不仅是多美滋　 汇源等多家国产果汁巨头卷入“烂果门”　 两性营养保健：哪些食物让男人更持久　 地沟油勾兑成调和油 检测仍无成熟技术　 中医食疗：用蜂蜜治咳嗽，标本兼治！　 常吃辛辣烫的食物易患消化道肿瘤　
评论列表
添加评论