✅✅C++ || Binary Search + DP|| Clear and Explained Code
Intuition\nBinary serach for trying out capacity and dp for checking its validity\n\n# Approach\nHere let\'s us consider the minimum capacity that u have to ret
# Intuition\nBinary serach for trying out capacity and dp for checking its validity\n\n# Approach\nHere let\'s us consider the minimum capacity that u have to return(ans) is between the maximum and min of nums elements.\nNow we will use "binary search" to check for a cap(mid = (start+end)/2).\nNow for this mid using "DP" we will find the number of elements that are less than or equal to mid in given nums array. if it comes greater than or equal to k then this mid can be a answer and we will try to find an ans less than this mid.\n\n# Complexity\n- Time complexity: O(N*LOG(N)) // calling dp function logn times\n\n- Space complexity: O(N*LOG(N)) // creating dp vector logn times \n\n# Code\n```\nclass Solution {\npublic:\n    int fun(int i,int mid,vector<int>& nums,int n,vector<int>& dp){\n        if(i>=n) return 0;\n        if(dp[i]!=-1)return dp[i];\n        int take = 0;\n        if(nums[i]<=mid){\n            take = 1 + fun(i+2,mid,nums,n,dp);\n        }\n        int not_take = fun(i+1,mid,nums,n,dp);\n        return dp[i]=max(take,not_take);\n    }\n    int minCapability(vector<int>& nums, int k) {\n      int n = nums.size();\n      int maxi = -1e9, mini = 1e9;\n      for(int i=0;i<n;i++){\n          mini = min(mini,nums[i]);\n          maxi = max(maxi,nums[i]);\n      }\n      int start = mini,end = maxi;\n      int ans = 0;\n      while(start<=end){\n          int mid = (start+end)/2;\n          vector<int> dp(n,-1);\n          int p = fun(0,mid,nums,n,dp);\n          if(p>=k){\n              ans = mid;\n              end = mid-1;\n          }\n          else{\n              start = mid+1;\n          }\n      }\n      return ans;\n    }\n};\n```
['C++']