[C++] Intuitive explaination - math and sorting (not DP)
Intuition\nFirst we can see that selecting an index for the operation more than once is not helpful. If we choose index i for step S_k, then the value at that i
# Intuition\nFirst we can see that selecting an index for the operation more than once is not helpful. If we choose index $$i$$ for step $$S_k$$, then the value at that index for the sum at that step will be 0, regardless of whether we chose it at some earlier step. For this reason, we also know that it wont make sense to take more than N steps.\n\nLets call the sum of all numbers in nums1, $$SN1$$, and the sum all of numbers in nums2, $$SN2$$.\n\nWe can see that if we selected no index at each step, then after $$S$$ steps, the sum would be $$SN1 + S*SN2$$. We also see that selecting an index for an operation will remove $$n1_i$$ and $$S_k*n2_i$$ from that naive sum, where $$S_k$$ is the step when that index is selected.\n\nFor example, lets say $$nums1[i] = 4$$ and $$nums2[i] = 3$$. If we select this index for step 3 out of 5, then the base value of 4 and the first 3 additions of 3 will be zeroed out, leaving only 2 multiples of 3:\nstep 0: 4\nstep 1: 4 + 3 = 7\nstep 2: 7 + 3 = 10 \nstep 3: 10 + 3 = 13 => selected to be 0 \nstep 4: 13 + 3 = 16 ------------------- 0 + 3 = 3 \nstep 5: 16 + 3 = 19 ------------------- 3 + 3 = 6\nFor a difference of $$19 - 6 = n1 + S_k * n2 = 4 + 3*3 = 13$$.\n\nSince we wont chose the same index more than once, if we use the max N steps, each index will be chosen once, giving us a final sum of $$SN1 + N*SN2 - \\sum_{i=0}^N(n1_i + S_k*n2_i)$$. To get the lowest total sum possible, we should pick $$n2_i$$ values from lowest to highest (pairing larger n2 values with larger $$S_k$$ coefficents, increasing the sum being subtracted, which in turn decreases the overall sum).\n\nHowever, we might be able to get a sum below the given value in less steps. We can do so by working backwards and deciding which index to not select when going from using S steps to using S-1 steps instead. In this case where we use S instead of N steps, the sum is $$SN1 + S*SN2 - \\sum_{i=0}^S(n1_i + S_k*n2_i)$$. When we remove an index, we are removing $$n1_i + S_k*n2_i$$ from the subtraction *and* reducing the coeficents of all indices chosen after that index by 1 (based on the step they are selected in).\n\nFor example, lets say we have the best sum for when we choose 3 indices. Then this sum looks like $$SN1 + 3*SN2 - ((n1_0 + n2_0) + (n1_1 + 2*n2_1) + (n1_2 + 3*n2_2))$$ where we assume the indices are sorted by the value of n2, so that $$n2_2$$ is the largest (the value of n1 doesn\'t affect the ordering and therefore it doesn\'t affect the coefficent either, but it does affect which index to remove as you\'ll see shortly). If we remove index 2, then we remove only $$n1_2 + 3*n2_2$$ and the new sum is $$SN1 + 2*SN2 - ((n1_0 + n2_0) + (n1_1 + 2*n2_1))$$. But if we remove index 0, then we are removing $$n1_0 + n2_0$$ as well as one instance of $$n2_1$$ and one instance of $$n2_2$$, for a new sum of $$SN1 + 2*SN2 - ((n1_1 + n2_1) + (n1_2 + 2*n2_2))$$ (note the new coefficents which are one less than in the sum with three indicies).\n\nWe want this removed amount to be as small as possible to keep the subtraction as large as possible (keeping the sum as low as possible). So for each number of steps, we calculate this value for each remaining index and select the one with the smallest value to be removed.\n\n\n# Approach\nFirst calculate the sum of each array.\n\nSort the arrays by the value in nums2.\n\nCalculate the ideal sum when taking N steps by using this order.\n\nThen iteratively remove one selection which will increase the sum by the least amount, checking at each step if we are below the target sum.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution\n{\npublic:\n\tint minimumTime(vector<int>& nums1, vector<int>& nums2, int x)\n\t{\n\t\tint n = nums1.size();\n\t\tint minTime = -1;\n\n\t\tvector<pair<int, int>> pairedNums;\n\t\tint n1Sum = 0;\n\t\tint n2Sum = 0;\n\t\tfor (int i = 0; i < n; ++i)\n\t\t{\n\t\t\tpairedNums.push_back(make_pair(nums2[i], nums1[i]));\n\t\t\tn1Sum += nums1[i];\n\t\t\tn2Sum += nums2[i];\n\t\t}\n\t\tsort(pairedNums.begin(), pairedNums.end());\n\n\t\tif (n1Sum <= x)\n\t\t{\n\t\t\treturn 0;\n\t\t}\n\n\t\tfor (int i = 0; i < n; ++i)\n\t\t{\n\t\t\tvector<pair<int, int>> valueIfRemoved;\n\t\t\tint sum = n1Sum + (n - i) * n2Sum - selectedSum(pairedNums, valueIfRemoved);\n\t\t\tif (sum <= x)\n\t\t\t{\n\t\t\t\tminTime = n - i;\n\t\t\t}\n\n\t\t\tauto minRemovedValue = min_element(valueIfRemoved.begin(), valueIfRemoved.end());\n\t\t\tpairedNums.erase(pairedNums.begin() + minRemovedValue->second);\n\t\t}\n\n\t\treturn minTime;\n\t}\n\nprivate:\n\tint selectedSum(vector<pair<int, int>>& selected, vector<pair<int, int>>& valueIfRemoved)\n\t{\n\t\tint sum = 0;\n\t\tint n = selected.size();\n\t\tint sumPrevMultipliers = 0;\n\t\tfor (int i = n - 1; i >= 0; --i)\n\t\t{\n\t\t\tint value = (i + 1) * selected[i].first + selected[i].second;\n\t\t\tsum += value;\n\t\t\tvalueIfRemoved.push_back(make_pair(value + sumPrevMultipliers, i));\n\t\t\tsumPrevMultipliers += selected[i].first;\n\t\t}\n\t\treturn sum;\n\t}\n};\n```
['Math', 'Sorting', 'C++']