Solved | C++🚀
IntuitionWe need to find the minimum capability (maximum value a house thief can rob) while ensuring that they rob exactly k houses without robbing adjacent hou
# Intuition
We need to find the **minimum capability** (maximum value a house thief can rob) while ensuring that they rob exactly `k` houses **without robbing adjacent houses**.

Since the **robbery capability is monotonic**, we can use **binary search** on the **capability threshold** to efficiently find the minimum valid value.

---

# Approach
1. **Binary Search Range**:
   - `min = 1` (smallest possible capability).
   - `max = max_element(nums)` (largest house value).

2. **Binary Search on Capability (`mid`)**:
   - Try a capability `mid = (min + max) / 2`.
   - **Greedy Selection**:
     - Iterate through `nums`, **picking non-adjacent houses** that have a value ≤ `mid`.
     - If we can rob at least `k` houses, reduce `max = mid` (try a smaller capability).
     - Otherwise, increase `min` (increase capability).

3. **Return `min`**, the smallest valid capability.

---

# Complexity
- **Time Complexity**:  
  $$O(N \log M)$$ where `N` is the number of houses and `M` is the maximum house value.

- **Space Complexity**:  
  $$O(1)$$ since only integer variables are used.

---

# Upvote 🚀
If this helped, **upvote** and keep coding! 🔥


![Screenshot 2025-03-16 at 3.53.13 AM.png](https://assets.leetcode.com/users/images/53a7f917-d322-479c-9247-8c9cc43ffa90_1742077410.5791554.png)

# Code
```cpp []
class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int max=*max_element(nums.begin(),nums.end()),min=1,mid=0,c=0,s=nums.size();
        while(min<max)
        {
            mid=(max+min)/2;
            c=0;
            for(int i=0;i<s;i++)
                if(nums[i]<=mid)
                {
                    c++;
                    i++;
                }
            if(c>=k)
            max=mid;
            else
            min=mid+1;
        }
        return min;
    }
};
```
['Array', 'Binary Search', 'C++']