✅Detailed Explaination||Prefix sum||dp||c++
\nThe only way to get to room i+1 is when you are visiting room i and room i has been visited an even number of times.\nLet understand with example \xA0\n\n    
\n**The only way to get to room i+1 is when you are visiting room i and room i has been visited an even number of times.**\nLet understand with example \xA0\n```\n      room number  ->  0 1 2 3 4 5\nlets take  nextVisit[]=[0,0,0,1,4,5] \n```\n```\n\u2705to go 1th room from 0th->0(odd),0(even)   //2 days\n\u2705to go 2th room from 1th->1(odd),0(odd),0(even),1(odd) why 0th visit is odd because there is no way \u2705to  go i+1 without visiting twice   //4 days\n\u2705to go 3rd room from 2->2,0,0,1,0,0,1,2    //8 days\n\u2705to go 4 from 3  -> 3,1,0,0,1,2,0,0,1,0,0,1,2,3 //14 days\n\u2705to go 5th from 4th->4,4 // 2days\nfinish\n``` \nCan You decode the pattern \n```\nfrom i to i+1-> i,ans of nextVisit[i] to i-1,i **\nin mathmatical term to go i+1th room day_taken=sum(day taken from nextVisit[i] to i -1)+2 (first + second visit at i)\ntake room 3 from above example \ndays_taken_to_reach_room4_starting from 3\n \xA0 \xA0 \xA0 \xA0 \xA0 =sumof(nextvisit[3] to i-1)+2\nans[3]=ans[1]+ans[2}+2\n         =4+8+2=14\n```\n```\nclass Solution {\npublic:\n    int m=1e9+7;\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n=nextVisit.size();\n        vector<long long> dp(n);\n        long long ans=0;\n        for(int i=0;i<n-1;i++){\n            long long day_taken_to_return_at_i=0;\n            for(int j=nextVisit[i];j<i;j++)\n                day_taken_to_return_at_i=(day_taken_to_return_at_i+dp[j])%m;\n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0dp[i]=(day_taken_to_return_at_i+2)%m;\n            ans=(ans+dp[i])%m;\n        }\n        return ans;\n    }\n};\n```  \n`Time-O(n*n)`\nThis solution will give us TLE \nCan we optimise this further ?\nAs we are calculating sum  \nfor(int j=nextVisit[i];j<i;j++) Obvious answer will be using Prefix sum\n```\nclass Solution {\npublic:\n    int m=1e9+7;\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n=nextVisit.size();\n        vector<long long> dp(n);\n        long long ans=2; \n        dp[0]=2;\n        for(int i=1;i<n-1;i++){\n            long long day_taken_to_return_at_i;\n            int start=nextVisit[i]; //our starting position \n            day_taken_to_return_at_i=dp[i-1]-(start>0?dp[start-1]:0);\n            dp[i]=(day_taken_to_return_at_i+2)%m; //current ans\n            ans=(ans+dp[i])%m; \n            dp[i]+=dp[i-1]; //prefix sum of days to visit 0->i\n        }\n        return ans;\n    }\n};\n``` \n`Time-O(n)`
['Dynamic Programming', 'Prefix Sum']