✅Fully Explained || Ant on Planks || Trilogy 2022 || C++
Intuition\n Describe your first thoughts on how to solve this problem. \nBefore solving this question, if you have solved the problem Ant on planks, it would he
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBefore solving this question, if you have solved the problem Ant on planks, it would help you a lot to think the next step in this question.\n\nSo the intuition is to think that image robots to pass each other and just ignore about collision and think after it. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSo now, after d time, we can calculate the position of every robot. Now we just need to find the distance between every pair.\nIt can be done in $O(n^2)$ but we should be able to do it in $O(n)$.\n\nNow visualize the following scenario.\n\n[A,B,C,D].\nEach letter represents final position of each robot in the number line.\nSo the distance can be calculated as below.\n\n$D \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ C \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ B$    \n$\nD-c\\ \\ \\ \\ \\ C-b \\ \\ \\ \\ \\ B -a\\\\\nD-b\\ \\ \\ \\ \\ C -a\\\\\nD-a\\\\\n$\nFrom this we can relate how we can use prefix sum.\nWe start with first index and keep prefix sum=0;\nNow when we are at $ith$ index there will be i robots before us. So we can multiply $i$ by $position[i]$ and subtract a prefix_sum.\n\nMake sure to use MOD properly.\n# Complexity\n- Time complexity:$O(n) + O(nlogn) + 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```\nclass Solution {\npublic:\n    int sumDistance(vector<int>& nums, string s, int d) \n    {\n        const int MOD = 1e9+7;\n        int n=nums.size();\n        for(int i =0;i<nums.size();i++)\n        {\n            long long temp=nums[i];\n            if(s[i]==\'R\') temp=temp+d;\n            else temp=temp-d;\n            nums[i]=temp;\n        }\n        sort(nums.begin(),nums.end());\n        long long ans=0;\n        long long pref=0;\n        for(int i =0;i<nums.size();i++)\n        {\n            ans = ans%MOD + (i*(long long)nums[i]-pref)%MOD;\n            pref = pref+nums[i];\n        }\n        return ans%MOD;\n        \n    }\n};\n```
['Brainteaser', 'Prefix Sum', 'C++']