C++ | O(N) | Prefix Sums | Basic Overview
The primary observation here is that all the rooms will be reached one after the other.\nSo, the number of days required to reach a particular room i would be e
The primary observation here is that all the rooms will be reached one after the other.\nSo, the number of days required to reach a particular room i would be equal to <b>cost[i - 1] + 1 + cost[i - 1] - cost[roomVisitedFromthelastroom] + 1</b>.\nThe states of the rooms are not important as all of them will always be reset to even values after the transition from room i to room i + 1; so they can always be assumed as even values.\nThe above things can easily be implemented via Prefix Sums.\n```\n#include<bits/stdc++.h>\nusing namespace std;\n\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n      vector<long long> costs(nextVisit.size());\n      long long modder = 1e+9 + 7;\n      for(int i = 1; i < costs.size(); i++)\n      {\n        costs[i] = costs[i - 1] + 1;\n        costs[i] %= modder;\n        costs[i] += costs[i - 1] - costs[nextVisit[i - 1]] + 1;\n        costs[i] %= modder;\n      }\n      int output = costs[nextVisit.size() - 1];\n      if(output < 0)\n      {output = modder + output;}\n      return output;\n    }\n};\n//Written by Namit Shah (Eclecticity).\n//Hack/Challenge this if you wish to salvage a few points off a destined-to-sink ship.\n\n```
[]