2560: House-Robber-IV
Medium

table of contents

Quite similar to yesterday’s problem, as you are meant to binary search the capability of the robber, and to see if it is valid or not.

You basically just:

code

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end());
        int ans;
        while (left <= right) {
            int mid = left - (left - right)/2;
            
            int count = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid) {
                    ++count;
                    ++i;
                    if (count == k) break;
                }
            }
            if (count == k) {
                ans = mid;
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }
};

complexity

learnings