Skip to content

3824. Minimum K to Reduce Array Within Limit

Description

You are given a positive integer array nums.

For a positive integer k, define nonPositive(nums, k) as the minimum number of operations needed to make every element of nums non-positive. In one operation, you can choose an index i and reduce nums[i] by k.

Return an integer denoting the minimum value of k such that nonPositive(nums, k) <= k2.

Β 

Example 1:

Input: nums = [3,7,5]

Output: 3

Explanation:

When k = 3, nonPositive(nums, k) = 6 <= k2.

  • Reduce nums[0] = 3 one time. nums[0] becomes 3 - 3 = 0.
  • Reduce nums[1] = 7 three times. nums[1] becomes 7 - 3 - 3 - 3 = -2.
  • Reduce nums[2] = 5 two times. nums[2] becomes 5 - 3 - 3 = -1.

Example 2:

Input: nums = [1]

Output: 1

Explanation:

When k = 1, nonPositive(nums, k) = 1 <= k2.

  • Reduce nums[0] = 1 one time. nums[0] becomes 1 - 1 = 0.

Β 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Solutions

We notice that as \(k\) increases, it becomes easier to satisfy the condition. This exhibits monotonicity, so we can use binary search to find the minimum \(k\).

We define the left boundary of the binary search as \(l = 1\) and the right boundary as \(r = 10^5\). In each binary search iteration, we calculate the middle value \(mid = \lfloor (l + r) / 2 \rfloor\) and determine whether the condition \(\text{nonPositive}(\text{nums}, k) \leq k^2\) is satisfied when \(k = mid\). If the condition is satisfied, we update the right boundary to \(r = mid\); otherwise, we update the left boundary to \(l = mid + 1\). When the binary search ends, the left boundary \(l\) is the minimum \(k\) we are looking for.

The time complexity is \(O(n \log M)\), where \(n\) and \(M\) are the length of the array \(\textit{nums}\) and the maximum range respectively. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minimumK(self, nums: List[int]) -> int:
        def check(k: int) -> bool:
            t = 0
            for x in nums:
                t += (x + k - 1) // k
            return t <= k * k

        l, r = 1, 10**5
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumK(int[] nums) {
        int l = 1, r = 100000;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(nums, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int[] nums, int k) {
        long t = 0;
        for (int x : nums) {
            t += (x + k - 1) / k;
        }
        return t <= 1L * k * k;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimumK(vector<int>& nums) {
        auto check = [&](int k) -> bool {
            long long t = 0;
            for (int x : nums) {
                t += (x + k - 1) / k;
            }
            return t <= 1LL * k * k;
        };

        int l = 1, r = 1e5;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func minimumK(nums []int) int {
    check := func(k int) bool {
        t := 0
        for _, x := range nums {
            t += (x + k - 1) / k
        }
        return t <= k*k
    }

    return sort.Search(100000, func(k int) bool {
        if k == 0 {
            return false
        }
        return check(k)
    })
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minimumK(nums: number[]): number {
    const check = (k: number): boolean => {
        let t = 0;
        for (const x of nums) {
            t += Math.floor((x + k - 1) / k);
        }
        return t <= k * k;
    };

    let l = 1,
        r = 100000;
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

Comments