Binary Search + Greedy Solution | C++
IntuitionATQ we need to find min. capability which can be used to rob at least k houses. I thought if i was given the value of capability can i check if it meet
# Intuition
ATQ we need to find min. capability which can be used to rob at least k houses. I thought if i was given the value of capability can i check if it meets the req. criteria. Also at some value all house can be robbed with. high capability so that was proof for predicate of binary search.

# Approach
Use binary serach on answer to find capability. Check if that capabilty satisfies condition of robbing atleast k houses. Greedily count if `nums[i] <= capability` since value of every house will be counted as 1.
Then if condition is true shift right bound otherwise left bound.

# Complexity
- Time complexity: $$O(nlog(1e9))$$

- Space complexity: $$O(1)$$

# Code
```cpp []
class Solution {
public:
    int minCapability(vector<int>& nums, int k)
    {
        int n = nums.size();

        auto chk = [&](int c) -> bool
        {
            int cnt = 0;

            for (int i = 0; i < n; ++i)
            {
                if (nums[i] <= c)
                {
                    cnt++;
                    i++;
                }
            }

            return cnt >= k;
        };

        int l = 1, r = 1e9, mid;
        while (l <= r)
        {
            mid = l + (r - l) / 2;

            if (chk(mid))
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        return r + 1;
    }
};
```
['C++']