[C#], Prefix sum, math
Intuition\n Describe your first thoughts on how to solve this problem. \n1. We can just add/subtract the d for each robot and it will work. Because collision he
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. We can just **add/subtract the `d`** for each robot and it will work. Because collision here works just like no collision happens.\n```\nExamples\n1.\n[-2,0,2], s = "RLL", d = 3\nd = 1, [-1, -1, 1] ->, <-, <-.  robots at -1(->, <-) will change direction\nd = 2, [-2,  0, 0] <-, ->, <-   robots at  0(->, <-) will change direction\nd = 3, [-3, -1, 1] <-, <-, ->\n\nIf just add/subtract d\n[1, -3, -1], we get the same result but unsorted\n\n2.\n[1,5], s = "RL", d = 5\nd = 1, [2, 4] ->, <-\nd = 2, [3, 3] <-, ->  robots at 3(->, <-), in the next second will change direction\nd = 3, [2, 4] <-, ->  passed through\nd = 4, [1, 5] <-, ->\nd = 5, [0, 6] <-, ->\n\nIf just add/subtract d\n[6, 0], we get the same result but unsorted\n\n3.\n[3,4], s = "RL", d = 2\nd = 1, [3, 4] <-, -> change direction, passed through\nd = 2, [2, 5] <-, ->  \n\nIf just add/subtract d\n[5, 2], we get the same result but unsorted\n\n```\n\n2. **Prefix sum**. To calculate distance between all pairs([i, j] = [j,i]) simple case is get brute-force,\nbut it will not fit to time limit(N^2). To we can calculate distance of all pairs in O(N) lets consider example:\n```\n[1,4,5,11]. \n(4-1) = 3\n(5-4) + (5-1) = 1 + 4 = 5\n(11-5) + (11-4) + (11-1) = 6+7+10=23\n23+5+3=31\n\n[1,4,5,11] Can be written as:\n(4-1) = 4*1 +(-1) = 5*1 - sum(1)\n(5-4) + (5-1) = 5*2 + (-4-1) = 5*2 - sum(4,1)\n(11-5) + (11-4) + (11-1) = 11*3 + (-5-4-1) = 11*3 - sum(5,4,1)\n\n```\n\n3. **Array sort**. What happens if array not ordered?\n```\n1.\n[1,3],  s="RL" d = 3\nd=1, [2,2]\nd=2, [1,3]\nd=3, [0,4]\n\n[4,0]\ni=0, res = 0*4 - 0 = 0, pref=4\ni=1, res=1*0 -4= -4.\n\n2.\n[0,2,4] \n(2-0)=2\n(4-2) + (4-0) = 2+4=6\n2+6=8\n\n[4,0,2] unordered\ni=0, res = 4*0 - 0 = 0, pref = 4\ni=1, res = 1*0 - 4=- 4, pref = 4 \ni=2, res = -4 + 2*2 - 4 =-4 + 4 -4 = -4\n\nSo, we didn\'t properly calculate distance\n\n```\n\n\n# Approach\n- **`long[] numsL`** - Used to handle if `nums[i] + d` overflow `int` size\n\n\n# Complexity\n- Time complexity:$$O(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```\npublic class Solution {\n    public int SumDistance(int[] nums, string s, int d) {\n        int N = nums.Length;\n        int mod = 1000000007;\n        long res = 0;\n        long pref = 0;\n        long[] numsL = new long[N];\n\n        for (int i = 0; i < N; i++) {\n            numsL[i] = nums[i] + (s[i] == \'L\' ? -d : d);\n        }\n\n        Array.Sort(numsL);\n\n        for (long i = 0; i < N; i++) {\n            res += i * numsL[i] - pref;\n            res = res % mod;\n            pref += numsL[i];\n        }\n\n        return (int)res;\n    }\n}\n\n```\n\n# Approach #2\nHere insted of prefix sum, used formula.\n```\nExample,\n[a,b,c,d]\n(b-a) + (c-a) + (d-a) = -3a + (b + c + d)\n(c-b) + (d-b)         = -2b + (c + d)\n(d-c)                 = -c + d\n\n= -3a + (-2b + b) + (-c +2c) + 3d\n= (0*a - 3*a) + (1*b - 2*b) + (2*c - 1*c) + (3*d - 0*d)\n\n[0,2,4], N = 2\ni=0, res += 0*0 - (3-0-1)*0 = 0\ni=1, res += 1*2 - (3-1-1)*2 = 0\ni=2, res += 2*4 - (3-2-1)*4 = 8\n\npublic class Solution {\n    public int SumDistance(int[] nums, string s, int d) {\n        int N = nums.Length;\n        int mod = 1000000007;\n        long res = 0;\n        long[] numsL = new long[N];\n        for (int i = 0; i < N; i++) {\n            numsL[i] = nums[i] + (s[i] == \'L\' ? -d : d);\n        }\n\n        Array.Sort(numsL);\n\n        for (long i = 0; i < N; i++) {\n            res += i * numsL[i];\n            res %= mod;\n            res -= (N - i - 1) * numsL[i];\n            res %= mod;\n        }\n\n        return (int)res;\n    }\n}\n```\nThanks for solutions from other posts, very helped\n\n
['Math', 'Prefix Sum', 'C#']