k
BAN USERAlmost an engineer in CS! Love to play soccer and passionate about koding!!
To find the node which forms the start of the loop:
1. use the double pointer (p and q) technique to establish that a loop exists. If a loop does exist, then the pointers meet on a node forming the loop.
2. if a loop does exist, then for each node (use a third pointer here, r) starting from the head, we check if it forms the start of the loop by using p to loop around and checking on each iteration if it meets r. If it meets then node r is the one, else increment r and repeat step 2
Step 1 requires O(n) time, while step 2 requires O(n^2) time. However, it requires O(1) space.
Is it possible in O(n) time and O(1) space??
Here we could use strings - string representation of the original number and the string representation of the number stored on a computer.
Given the number N, lets just store it using appropriate data type. Then, we get a string of this stored value. Lets now compare this string with the actual number entered as a string. If they equal, then bingo - we can store it accurately.
Perform a level order traversal of the tree - uses the breadth first search technique.
Since the queue in this technique will maintain references to the nodes in the tree, all that remains is we link up the elements in the queue which are already placed in order (dont delete the elements in the queue during the breadth first search, instead lets just have a pointer which points to the head of the queue and is incremented on each iteration).
This would be a O(n) algorithm with O(n) space!!
By working on a few examples I realized that the if(i == start) part of the above code is executed only for odd values of 'n'.
- k June 23, 2007For odd values of 'n' say n=11, the sequence of movements that we have are:
1 - 2 - 4 - 8 - 16 - 11 - 1
3 - 6 - 12 - 3
5 - 10 - 20 - 19 - 17 - 13 - 5
7 - 14 - 7
9 - 18 - 15 - 9
Each of these sequences have only one ascent. While for even values of n, say n = 10, the sequence is:
1 - 2 - 4 - 8 - 16 - 13 - 7 - 14 - 9 - 18 - 17 - 15 - 11 - 3 - 6 - 12 - 5 - 10 - 1