# 2560. House Robber IV

## Problem Statement

<br>

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he **refuses to steal from adjacent homes**.

The **capability** of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array `nums` representing how much money is stashed in each house. More formally, the `ith` house from the left has `nums[i]` dollars.

You are also given an integer `k`, representing the **minimum** number of houses the robber will steal from. It is always possible to steal at least `k` houses.

Return *the **minimum** capability of the robber out of all the possible ways to steal at least* `k` *houses*.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [2,3,5,9], k = 2
</strong><strong>Output: 5
</strong><strong>Explanation: 
</strong>There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,7,9,3,1], k = 2
</strong><strong>Output: 2
</strong><strong>Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= (nums.length + 1)/2`

## Intuition

```
Approach: 

To find minimun of maximum,
With binary search go towards minimum, while finding out if that mid satisfy
The maximum
```

### Links

<https://leetcode.com/problems/house-robber-iv/description/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool check_cap(vector<int>& nums, int k, int mid){
        int i=0;
        while(i<nums.size()){
            if(nums[i] <= mid){
                i += 2;
                k--;
            }
            else
                i++;
            
            if(k == 0)
                return true;
        }

        return false;
    }

    int minCapability(vector<int>& nums, int k) {
        int low= *min_element(nums.begin(), nums.end());
        int high= *max_element(nums.begin(), nums.end());
        int ans;
        while(low<=high){
            int mid = low + (high-low)/2;
            if(check_cap(nums, k, mid)){
                ans = mid;
                high = mid-1;
            }
            else
                low = mid + 1;
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###