C# Prefix Sum O(m + n) time O(1) space
Intuition\nTo get to success we need to check if we can compensate potion power with our spell power. So we need to calculate neededSpellCost for each potion. A
# Intuition\nTo get to ```success``` we need to check if we can compensate potion power with our spell power. So we need to calculate ```neededSpellCost``` for each potion. As it is an integer division we need to add 1 when it can\'t be divided to satisfy the requirement. After that we can see which spell can be used with which potion to make needed power.\n\n# Approach\n```neededSpellCost``` can be quite big, such that we won\'t have any possible spell at all, such cases just ignored.\n\nDuring the calculation of ```neededSpellCost``` we starting to build up our ```prefixSum```. After the loop on potions we will have ```prefixSum``` sloted with the number of each spell required.\n\nBut any ```k``` spell power can also be used to cover any less powerful spell. So we are going through ```prefixSum``` and accumulate it.\n\nLast run just goes through potions and sees how many each potion can cover.\n\n# Complexity\n- Time complexity: ```O(m + n + 100000)``` => ```O(m + n)```\n\n- Space complexity: ```O(100000)``` => ```O(1)```\n\n# Code C#\n```\npublic class Solution {\n    public int[] SuccessfulPairs(int[] spells, int[] potions, long success)\n        {\n            var limit = 100001;\n            var prefixSum = new int[limit];\n            for (var i = 0; i < potions.Length; i++)\n            {\n                var neededSpellCost = success % potions[i] == 0\n                    ? success / potions[i]\n                    : success / potions[i] + 1;\n\n                if (neededSpellCost < limit)\n                    prefixSum[neededSpellCost]++;\n            }\n\n            for (var i = 1; i < prefixSum.Length; i++)\n                prefixSum[i] += prefixSum[i - 1];\n\n            var result = new int[spells.Length];\n            for (var i = 0; i <  spells.Length; i++)\n                result[i] = prefixSum[spells[i]];\n\n            return result;\n        }\n}\n```
['Prefix Sum', 'C#']