C++ | Partial Sum
Hello Everyone\n\nBy reading the question we understand that we need to check whether we can reach from first index of given string to the last index by jumping
Hello Everyone\n\nBy reading the question we understand that we need to check whether we can reach from first index of given string to the last index by jumping only to the indexes with \'0\' character and also following the rule that\n\n* Length of jump should **atleast** be of minJump length from our existing place.\n* Length of jump should **not exceed** maxJump length from our existing place.\n\nBy looking at the above rules we get to the conclusion that to know whether we can reach to the last index from the index where we are standing, we need to check all the indexes from **(ith + minJump)** to the **(ith + maxJump)** indexes inclusively. So, we should iterate in reverse order and **turn invalid \'0\' to \'1\'** so that lower indexes don\'t consider them as a valid step.\n\nNow we have developed the base idea, but if we do the iteration from minJump index to the maxJump index for each and every index. We will get a **TLE** as our **Time complexity would be O(N*N)**.\n\n```\n// This code will give TLE\nclass Solution {\npublic:\n    bool canReach(string s, int minJ, int maxJ) {\n\t    int l = s.length();\n        if(minJ >= l || s[l-1] == \'1\'){\n            return false;\n        }\n        if(maxJ >= l-1){\n            return true;\n        }\n        for(int i=l-2; i>=0; i--){\n            if(s[i] == \'1\') continue;\n            bool check = false;\n            for(int j=minJ; j<=maxJ; j++){\n                if(i+j >= l) break;\n                if(s[i+j] == \'0\'){\n                    check = true;\n                    break;\n                }\n            }\n            if(!check){\n                s[i] = \'1\';\n            }\n        }\n        return s[0] == \'0\';\n    }\n};\n```\n\n**So can we do to solve the above problem of repetitive iterations ?**\n\nIf we observe carefully what we are acctually looking in for in those repetitive iterations is that whether there is a \'0\' in the jumping range from current index (remember we are turning all invalid \'0\' to \'1\').\n\nFrom this we can come to the fact that if sum of all characters in integer from is less then the distance between minJump and maxJump the there is a valid \'0\' character we can use to reach last index.\n\nSo as the concept of managing a sum has came to our mind, we can use a rec vector the keep a track of this but still the problem of repetitive iteration is not yet solved. For this we can use the partial sum method in reverse order. So, more like postfix sum :)\n\nBut remember that we are constantly tweaking the characters in the string in realtime while iterating the string. So, we need to aassign values to **rec vector** in real time as we are traverseing the string and turing the characters.\n\nThe above discussed idea has been implemented in below **C++ code**.\n\n```\nclass Solution {\npublic:\n    bool canReach(string s, int minJ, int maxJ) {\n        int count, dist, l = s.length();\n\n        if(minJ >= l || s[l-1] == \'1\'){\n            return false;\n        }\n        if(maxJ >= l-1){\n            return true;\n        }\n        vector<int>rec(s.length(), 0);\n\n        for(int i=l-2;i>=0;i--){\n            if(s[i] == \'1\' || i + minJ >= l){\n                rec[i] = rec[i+1] + 1;\n                continue;\n            }\n\n            if(i + maxJ >= l-1){\n                count = rec[i + minJ];\n                dist = l - (i + minJ);\n            }else{\n                count = rec[i + minJ] - rec[i + maxJ + 1];\n                dist = maxJ - minJ + 1;\n            }\n            if(count == dist){\n                s[i] = \'1\';\n                rec[i] = rec[i+1] + 1;\n            }else{\n                rec[i] = rec[i+1];\n            }\n        }\n        return s[0] == \'0\';\n    }\n};\n```\n\nThis is my first post with explanation, any suggestions to improve would be highly appreciated.
['C']