Binary Search Algorithm to Find the Smallest Divisor Given a Thr

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

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

推荐阅读：
作文写作指导：小学生作文该怎么写？　 小学作文需增长孩子的视野，鼓励孩子表达　 六年级劳动节作文　 五年级作文：不该丢失的童年色彩　 六年级作文：我和秋天有个约会　 数学故事：流传久远的算术趣题　 趣味数学：什么是完全数　 数学小故事：高斯巧解算术题　 数学趣味故事：测量金字塔的高度　 湖南卫视在线直播-湖南卫视直播在线观看「高清」　
评论列表
添加评论