Tarang
BAN USERThis solution is wrong.. lets see how..
take the string as "abcd"
in first call you make it "dbca"
then "dcba".. its reversed.. but wait.. n is still far from 0...
you reverse again it to.. "dbca".
then "abcd"..
So my friend.. make the recursion calls till n reaches ceil(n/2) (ceil as you are coming from n to middle; in case of odd characters the middle char remains at its original place.)
modification
1. search index exponentially 0,1,2,4,8,16,....
2. when you encounter 1 at any index, it means the transition 0->1 lies within x/2 and x
Till this step the above algorithm is correct.
But what if x is 100 million?? you do not want to operate a binary search on 50 million numbers. We already have a function which performs exponential search.
therefore 3rd step :
3. Recursive call to exponential search function which will now start at x/2, x/2 +1, x/2 + 2, x/2 + 4, x/2 +8, x/2 + 16....
If you know at which node the loop originates then you can easily find the last node in the loop.
To find where the loop starts, apply the tortoise and hare concept of fast and slow pointer. When you run two pointers from the head with speed 1 and 2, they both meet at a certain node say X.
Now this node X will be at the same distance from the origin of loop as distance between head and origin of loop.
In your case above, the two pointers meet at node 8.
8->9->10->4
1->2->3->4
These lengths will always be same. Try any case you like.
Cheers
A better solution with time complexity O(n) and space complexity O(1).
- Tarang August 02, 2013Use the above algorithm without concatenating the string. (i.e. traverse only the original string)
But run the 'for' loop 2*size (same as above).
Just use index as ( i mod size ) and ((answer+offset) mod size). It will automatically make indices within the range.