Welcome to Subscribe On Youtube

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)$.

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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)
	})
}


  • 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;
}

All Problems

All Solutions