✅4 Lines | Binary Search | C++ | Python | Java | Go | Javascript  
💡 Insights
The other versions of this question are related to dp but surprisingly when you come across the 4th variant of House Robber series, you expect it to
# 💡 Insights
- The other versions of this question are related to dp but surprisingly when you come across the 4th variant of **House Robber** series, you expect it to be the toughest dp question in the series so far but it's actually a binary search problem.
- What does this question ask for?
    - Find the smallest possible value of `m` where robbing **at least k houses** while skipping adjacent ones is possible.
- So basically, we binary search over the range `1` to `1e9` and check if we can rob `k` houses when the max house value we can rob is `mid`:
    - If `nums[i] <= mid`, we rob it and skip the next house.
    - Otherwise, we move to the next house.
- If we can't rob at least `k` houses for the current `mid`:
    - We increase `left` → `left = mid + 1`.
    - Else, we decrease `right` → `right = mid`.


---
# 👀 Visualization
- Lets say for the array - `[2, 3, 5, 7, 8, 12]`
- Here when we start searching from `1e9` and keep reducing it by half , it keeps saying that we can rob `3` houses.
- After we reach `mid = 5` we can rob `3` houses , while if `mid = 4` then we can rob `2` houses.
- Therefore, the answer is `5`.

| Iteration | Left  | Right       | Mid         | canRob |
|-----------|-------|------------|------------|--------|
| 1.         | 1     | 1000000000 | 500000000  | 3      |
| 2.         | 1     | 500000000  | 250000000  | 3      |
| 3...         | 1     | 250000000  | 125000000  | 3      |
| 28.        | 1     | 7          | 4          | 3      |
| 29.        | 1     | 5          | 3          | 2      |
| 30.        | 4     | 5          | 4          | 2      |
| 31.        | 5     | 5          | 5          | 3      |

- Note that here the **30th iteration** is **invalid** , as the `canRob` changes from `3` to `2`. Therefore , we keep increasing `left` until we reach a position where the value of `mid` is maximum possible while satisfying `k` houses atleast (3 in this case).

---
# 💻 Implementation
```cpp []
class Solution {
public:
        int minCapability(vector<int>& nums, int k , int left = 1,int right = 1e9) {
        while(left < right) { 
        int mid = (left + right) / 2, canRob = 0; 
        for(int i = 0; i < nums.size() && canRob < k; i += nums[i] <= mid ? 2 : 1) 
            canRob += nums[i] <= mid; canRob < k ? left = mid + 1 : right = mid; 
        }
    return left;
    }
};
```
```Python []
def minCapability(nums, k, l=1, r=10**9):
    while l < r:
        m, t, i = (l + r) // 2, 0, 0
        while i < len(nums) and t < k:
            if nums[i] <= m:
                t += 1
                i += 2
            else:
                i += 1
        l, r = (m + 1, r) if t < k else (l, m)
    return l
```
```Java []
public int minCapability(int[] nums, int k) {  
    int l = 1, r = 1000000000;  
    while (l < r) { int m = (l + r) / 2, t = 0, i = 0;  
    for (; i < nums.length && t < k; i += nums[i] <= m ? 2 : 1) t += nums[i] <= m ? 1 : 0;  
    if (t < k) l = m + 1; else r = m; }  
    return l;  
}  
```
```Javascript []
function minCapability(nums, k) {  
    let l = 1, r = 1e9;  
    while (l < r) { let m = (l + r) >> 1, t = 0, i = 0;  
    while (i < nums.length && t < k) t += nums[i] <= m, i += nums[i] <= m ? 2 : 1;  
    t < k ? l = m + 1 : r = m; }  
    return l;  
}
```
```Go []
func minCapability(nums []int, k int) int {  
    l, r := 1, 1000000000  
    for l < r { m, t, i := (l+r)/2, 0, 0  
    for i < len(nums) && t < k { if nums[i] <= m { t++; i += 2 } else { i++ } }  
    if t < k { l = m + 1 } else { r = m } }  
    return l  
}
```
['Binary Search', 'Python', 'C++', 'Java', 'Go', 'JavaScript']