✔C++|Binary Search | Beats 100%🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n- Since if we see it is a mini-max problem beacuse here we have to find minimize the ma
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Since if we see it is a mini-max problem beacuse here we have to find minimize the maximum amount of money house  which robber steal.\n- Use binary search and greedy appraoch for checking for a particular mid if our `taken >=k` then we need to decrease the mid i.e `high=mid-1`\nif `taken < k` then `low=mid+1;`.\n- Greedy approach will check if our guess i.e mid is greater than k or less than k houses in which robber can rob. SO iterate over the array and pick any k non-adjacent elements that are smaller than our mid . \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int minCapability(vector<int>& arr, int k) {\n        int low=*min_element(arr.begin(),arr.end());\n        int high=*max_element(arr.begin(),arr.end());\n        int n=arr.size();\n        while(low<=high){\n            int mid=low+(high-low)/2;\n            int taken=0;\n            for(int i=0;i<n;i++)\n               if(mid>=arr[i])taken++,i++;\n             if(taken<k)low=mid+1;\n            else high=mid-1;\n        }\n        return low;\n    }\n};\n```
['Array', 'Binary Search', 'Dynamic Programming', 'C++']