C++/Python Math sum||50ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nLet the non-decreasing sequence is given\n\na_0\leq a_1\leq\cdots \leq a_i\leq \cdots a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet the non-decreasing sequence is given\n$$\na_0\\leq a_1\\leq\\cdots \\leq a_i\\leq \\cdots a_{n-1}\n$$\nConsider the computation\n$$\n\\sum_j|a_j-a_i|=\\sum_{i<j}a_j-a_i+\\sum_{j<i}a_i-a_j \\\\\n=\\sum_{i<j}a_j-(n-i-1)a_i+ia_i-\\sum_{j<i}a_j\\\\\n=\\sum_{i<j}a_j+(2i-n+1)a_i-\\sum_{j<i}a_j\n$$\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/FGDkETbwWHc?si=Ag7otErPwleFlz10](https://youtu.be/FGDkETbwWHc?si=Ag7otErPwleFlz10)\nLet A[i]=$\\sum_{j<i}a_j$, B[i]=$\\sum_{i<j}a_j$\nUse prefix sum & suffix sum to solve.\n![448px-Gradient_descent.svg.png](https://assets.leetcode.com/users/images/e17c43ee-8c3f-4fb4-a364-01fd0b3ec922_1700873659.1309502.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code 50ms Beats 100%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        int n=nums.size();\n        nums.push_back(0);//Adding 0 for avoid of if-branch in the loop\n        int A=0, B=accumulate(nums.begin()+1, nums.end(), 0);\n        vector<int> ans(n, 0);\n        #pragma unroll\n        for(int i=0; i<n; i++){\n            ans[i]=(2*i-n+1)*nums[i]+B-A;\n            A+=nums[i];\n            B-=nums[i+1];\n        }\n        return ans;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# A variant solution where B beginning with sum(nums)\n```C++ []\n\nclass Solution {\npublic:\n    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {\n        int n=nums.size();\n        int A=0, B=accumulate(nums.begin(), nums.end(), 0);\n        vector<int> ans(n, 0);\n        int i=0;\n        #pragma unroll\n        for(int x: nums){\n            ans[i++]=(2*i-n)*x+B-A;\n            A+=x;\n            B-=x;\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n        n=len(nums)\n        A=0\n        B=sum(nums)\n        ans=[0]*n\n\n        for i, x in enumerate(nums):\n            ans[i]=(2*i-n)*x+B-A\n            A+=x\n            B-=x\n        return ans\n```\n```Java []\nclass Solution {\n    public int[] getSumAbsoluteDifferences(int[] nums) {\n        int n=nums.length;\n        int A=0;\n        int B=Arrays.stream(nums).sum();\n        int [] ans=new int[n];\n        int i=0;\n        for(int x : nums){\n            ans[i]=(2*i-n)*x+B-A;\n            A+=x;\n            B-=x;\n            i++;\n        }\n        return ans;   \n    }\n}\n```\n```C []\n/**\n * Note: The returned array must be malloced, assume caller calls free().\n */\n#pragma GCC optimize("O3")\nint* getSumAbsoluteDifferences(int* nums, int n, int* returnSize){\n    *returnSize=n;\n    int A=0;\n    int B=0;\n    #pragma unroll\n    for(register i=0; i<n; i++)\n        B+=nums[i];\n    int *ans=(int*)malloc(sizeof(int)*n);\n    #pragma unroll\n    for(register i=0; i<n; i++){\n        ans[i]=(2*i-n)*nums[i]+B-A;\n        A+=nums[i];\n        B-=nums[i];\n    }\n    return ans;\n}\n```\n
['Math', 'C', 'Prefix Sum', 'C++', 'Java', 'Python3']