# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/2560.-house-robber-iv.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.