[c++] | (4 Approaches) | Easy to Advanced |
//Approach 1: simple iterative O(n^2) without prefix sum\n\n    vector answerQueries(vector& nums, vector& queries) {\n        vector ans(queries.size());\n    
**//Approach 1: simple iterative O(n^2) without prefix sum**\n\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        vector<int> ans(queries.size());\n        int j;\n        \n        sort(nums.begin(), nums.end());\n        for (int i = 0; i < queries.size(); i++)\n        {\n            int size = 0;\n            int sum = 0;\n            for (j = 0; j < nums.size(); j++)\n            {\n                if (sum + nums[j] <= queries[i]) \n                {\n                    sum += nums[j];\n                    size++;\n                }\n                else \n                    break;\n            }\n            ans[i] = size;\n        }\n        return ans;\n    }\n\n**#Approach 2: iterative O(n^2) using prefix sum**\n\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        int n = nums.size();\n        int q = queries.size();\n        \n        vector<int> ans(q);\n        \n        sort(nums.begin(), nums.end());\n        \n        //prefix sum\n        vector<int> preSum(n);\n        for (int i = 0, sum = 0; i < n; i++)\n        {\n            sum += nums[i];\n            preSum[i] = sum;\n        }\n        \n        for (int i = 0; i < q; i++)\n        {\n            int j = 0;\n            while (j < n )\n            {\n                if (preSum[j] <= queries[i]) \n                {\n                    j++;\n                }\n                else \n                    break;\n            }\n           ans[i] = j;\n        }\n        return ans;\n    }\n\n\n**# Approach 3: using upper bound, Time: O(nlogn + m) | Space: O(1)**\n\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        int n = nums.size();\n        int m = queries.size();\n        sort(nums.begin(), nums.end());\n        \n        //prefix sum -> \n        for (int i = 1; i < n; i++)\n        {\n            nums[i] += nums[i-1];\n        }\n       //binary search (using upper bound) \n        \n        for (int i = 0; i < m; i++)\n        {\n            queries[i] = upper_bound( nums.begin(), nums.end(), queries[i] ) - nums.begin();\n        }\n        return queries;\n\t}\n\n\nEXPLANATION:\n\nLower bound: first element that is greater-or-equal.\nUpper bound : first element that is strictly greater.\n\nqueries[i] = upper_bound(nums.begin(), nums.end(), queries[i])  - nums.begin(); \n\n//upper bound() -> returns iterator of first element that is greater than queries[i] e.g (X + 1)th iterator, but we need less or equal(i.e X th iterator), \n//nums.begin() -> returns iterator to the first element (i.e 1th iterator) ,\ntherefore upper bound() - nums.begin() = (X+1) - 1 = Xth element.\n\n\n\n**#Approach 4: Same as above but manual binary search**\n\n\tint binary(vector<int> &n, int target)\n    {\n        int s = 0, e = n.size() - 1, m;\n\t\t\n        while (s <= e)\n        {\n            m = s + (e-s)/2;\n            if (n[m] > target)\n                e = m - 1;  //it\'ll point to the required element eventually in case target\n\t\t\t\t\t\t\t\t  // is not present in nums.\n            else if (n[m] < target)\n\t\t\t\ts = m + 1;   //s will pass the required element if(target <   n[m]);\n\t\t\t\t\t\n            else             // if (target == n[m])\n                return m + 1;\n        }\n        return \n           e+1;\n    }\n    vector<int> answerQueries(vector<int>& n, vector<int>& q) \n    {\n        int a = n.size(), b = q.size();\n        sort(n.begin(), n.end());\n        \n        //prefix sum -> \n        for (int i = 1; i < a; i++)\n            n[i] += n[i-1];\n        \n       //binary search \n        for (int i = 0; i < b; i++)\n        {\n            q[i] = binary(n, q[i]);\n        }\n        return q;\n    }\n\n\n
['Binary Search', 'C', 'Sorting', 'Prefix Sum', 'C++']