C++ 2 approaches( Binary search and BFS)
Binary search Approach:\nWe maintain a vector reachable which contains the list of reachable zero indices, (reachable means that the specific zero index can be 
**Binary search Approach:**\nWe maintain a vector ***reachable*** which contains the list of reachable zero indices, (reachable means that the specific zero index can be reached from the beginning index).\nAt index i, we continue if s[i] is \'1\'.\nif s[i] is \'0\', we do a binary search in the reachable vector to find an index(say k) such that i-k>=minjump and i-k<=maxjump. If difference is less than minjump, we definitely need to decrease the index so we search in the lower half. if difference is higher than maxjump,we definitely need to increase the index, so we search in the upper half.\n\nTime Complexity: O(N*logN)\nSpace Complexity: O(N)\n\n```\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        if(s[s.size()-1]==\'1\')\n            return false;\n        vector<int>reachable;\n        reachable.push_back(0);\n        int lo,hi,mid,diff;\n        for(int i=1; i<s.size(); i++)\n        {\n            if(s[i]==\'1\')\n                continue;\n            lo=0,hi=reachable.size()-1;\n            while(lo<=hi)\n            {\n                mid=lo+(hi-lo)/2;\n                diff=i-reachable[mid];\n                if(diff>=minJump && diff<=maxJump)\n                {\n                    reachable.push_back(i);\n                    break;\n\n                }\n                else if(diff<minJump)\n                {\n                    hi=mid-1;\n                }\n                else\n                {\n                    lo=mid+1;\n                }\n            }\n        }\n        return (reachable.back()==s.size()-1);\n    }\n};\n```\n\n\n**Breadth first search approach**\n\n```\n/* Logic:\n\nBFS approach: we model this problem as a graph problem. the array elements will be the nodes and for every node i, the edges will be from i to elements in the range [i+minjump,min(n-1,i+maxjump)]. But here the time complexity will be O(n*n) as the # of edges will be equal to n*(maxJump-minJump) which in the worst case can be equal to O(n*n). \nHow do we optimize: eg: 00000, minJump=1, maxJump=3.\n--> in first iteration: indexes 1 to 3 will be inserted in the queue. In second iteration, the edges will be in the range of [2,4], but we will not insert the nodes 2 and 3 since they have already been inserted in the queue. So as an optimization, we start from 4 instead of 2 since 2 and 3 will be repeated. Thus we keep a track of the maxvisited node in the queue. So, the edges for node i will start from max(maxvisited+1,i+minJump).\n\nIn this way, the edges will sum up to n.\nSo, the time complexity of the algorithm is O(n)\n*/\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        if(s[s.size()-1]==\'1\')\n            return false;\n        int len=s.size();\n        //BFS approach\n        int max_vis=0;\n        queue<int>q;\n        q.push(0);\n        int currnode;\n        while(!q.empty())\n        {\n            currnode=q.front();\n            q.pop();\n            if(currnode==len-1)\n                return true;\n            for(int j=max(max_vis+1,currnode+minJump); j<=min(currnode+maxJump,len-1); j++)\n            {\n                if(s[j]==\'0\')\n                {\n                    q.push(j);\n                    \n                }\n            }\n            max_vis=min(currnode+maxJump,len-1);\n        }\n        return false;\n    }\n};\n```
[]