Binary Search Algorithm to Find the Smallest Divisor Given a Thr

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

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

推荐阅读：
樱花|小学作文　 猜谜语 胡耀宇|小学作文　 小心老师性侵犯|小学作文　 描写圣诞节的小学生作文_圣诞节　 关于元宵节的小学生作文300字_在元宵节的夜晚　 清明节_关于清明节的小学生记事作文650字　 关于春节的小学生作文_我们中国的传统节日——春节　 漂亮的鸽子|小学作文　 找春天（赵芮睿）|小学作文　 可爱的小金鱼|小学作文　
评论列表
添加评论