Day92||Binary Search very Easy Solution
Intuition and Approach\nWe have implemented Binary Search to Solve the problem\n\nSo, Condition to use binary tree is that array must be sorted\n\nSo, we used t
# Intuition and Approach\nWe have implemented Binary Search to Solve the problem\n\nSo, Condition to use binary tree is that array must be sorted\n\nSo, we used the inbuilt sort function.\n\nNow to solve the problem many of you have already tried to do it in O(n^2) order (Code given below) but it is giving the TLE.\n```\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& s, vector<int>& po, long long success) {\n        vector<int> v;\n        int count=0;\n\n        for(int i=0;i<s.size();i++){\n            for(int j=0;j<po.size();j++){\n                if(s[i]*po[j] >= success){\n                    count++;\n                }\n            }\n            v.push_back(count);\n            count=0;\n        }\n        return v;\n    }\n};\n```\n(In above approach we are simply calulating the product of two array and comparing it to Success)\nSo, to overcome the TLE we have to think a way to minimize our search space and hence Binary Search came into play\n\nThere is an **Observation** for sorted array which is that if a current potion muliplied with current spell and if it greater than Success then all elements ahead of that position will be a satisfiable answer.\n```\ne.g. spells=[5,3,1] , potion=[1,2,3,4,5] , Success=7\nAns: 5*1=5, 5*2=10, 5*3=15, 5*4=20, 5*5=25\n              |\n              |--from here, all ahead value will be greater than Success\nSimilarly, 3*1=3, 3*2=6, 3*3=9...\n                           |\n                           |--from here, all value satisfy the Success\n*Hence, we have to calculate or find the leftmost value which satisfies \nthe relation.\n```\nSo, We are using binary search to find that value by using the condition you can check it in the code.\n\n**Upvote If you like.**\n# Complexity\n- Time complexity:O(n*log(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& s, vector<int>& po, long long success) {\n        vector<int> v;\n        //sorting the potion array\n        sort(po.begin(),po.end());\n\n        for(int i=0;i<s.size();i++){\n            int count=0;\n            int l=0,r=po.size()-1;\n            int mid=l + (r-l)/2;\n            //Using Binary Search on potion array\n            while(l<=r){\n                if(s[i]*1ll*po[mid] >= success){//1LL is securely integer overflow\n                    count=po.size()-mid;\n                    r=mid-1;\n                }\n                else{\n                    l=mid+1;\n                }\n                mid= l + (r-l)/2;\n            }\n            v.push_back(count);\n        }\n        \n        return v;\n    }\n};\n```
['Math', 'Binary Search', 'Sorting', 'C++']