C++ - Sort + prefix sum
Intuition\nWhen robot collide, it changes direction. We do not need to worry about changing direction of the robot. Pleae see below example to understand it bet
# Intuition\nWhen robot collide, it changes direction. We do not need to worry about changing direction of the robot. Pleae see below example to understand it better. \nA (at 4 and traveling right ) and B(at 5 and traveling left). When they collide A and B changes direction so you can imaging A becomes robot B and B becomes A. \n\nAfter finding Robot position after d seconds, we can simply use prefix distance method to find the distance between all pairs. \n\n# Complexity\n- Time complexity:\nO(NLOGN) -> N = number of robots\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n    int sumDistance(vector<int>& nums, string s, int d) {\n        for (int i=0;i<nums.size();i++) nums[i]+=(s[i]==\'L\'?-d:d);\n        sort(nums.begin(),nums.end());\n        long long ans=0,pre=0;\n        int MOD=1000000007;\n        for (int i=1;i<nums.size();i++){\n            //cout << nums[i-1] << " to " << nums[i] << endl;\n            pre = (pre + 1LL*(1LL*nums[i]-1LL*nums[i-1])*(i))%MOD;\n            ans = (ans + pre)%MOD;\n        }\n        return ans;\n    }\n};\n```
['Sorting', 'Prefix Sum', 'C++']