I solved it without any temp variables and the solution works like magic. Suppose the sequence is A1, A2, A3, A4, A5 B1, B2, B3, B4, B5
Now here N = 5. I had to perform 1+2+3+4 = N(N-1)/2 swaps to get the desired order. The scheme work like this. At step 1, perform only one Swap - A5, B1 Now the sequence become A1, A2, A3, A4, B1 A5, B2, B3, B4, B5 At step 2, perform two swaps <A4,B1> and <A5,B2> Now the sequence will become A1, A2, A3, B1, A4 B2, A5, B3, B4, B5 At Step 3, perform three swaps <A3,B1> <A4,B2> and <A5,B3> Now the sequence will become A1, A2, B1, A3, B2 A4, B3, A5, B4, B5 Similarly at step 4, perform 4 swaps Sequence would be A1, B1, A2, B2, A3, B3, A4, B4, A5, B5. This solution is space optimized and has a higher time complexity O(n2) On Tue, Jul 5, 2011 at 12:06 PM, vikas <[email protected]> wrote: > We can solve this in O(n) time like this: > Let me say total elements in array is 2N such that 1 to N are a's and > N +1 to 2N (which I will again refer to as 1 to N) are b's If an > element is on first 1 to N (an 'a') and has index i then in the final > array its position index (in the final 2N array) will be i+(i-1) > [current index + no. of positions lying to the left]. If an element is > on the second 1 to N (the b's series) and has index j then in the > final array of 2N, its index will be 2j. With this observation we > start with the last element of first series, the a's and find its > final position in result array. Place the element in final position. > Take the element which is lying there and find this elements new > position and go on. Example: start with temp=a6 (the last element of > furst series) a1,a2,a3,a4,a5,a6,b1,b2,b3,b4, > b5,b6 temp=a6, final > position of a6 = 6+(6-1) = 11. Put a6 in eleventh position and take > the element at 11th position into temp: So now > a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,a6,b6 and temp = b5. Final position of > b5 = 2*5 = 10. Put b5 at 10th position and take previous element in > temp. So now a1,a2,a3,a4,a5,a6,b1,b2,b3,b5,a6,b6 and temp = b4. Final > position of b4 = 2*4 = 8. Put b4 at 8th position and take previous > element at 8th in temp. So now a1,a2,a3,a4,a5,a6,b1,b4,b3,b5,a6,b6 and > temp = b2, going this way we > will have next position of b2 = 2*2=4 > a1,a2,a3,b2,a5,a6,b1,b4,b3,b5,a6,b6 and temp = a4: next position of a4 > = 4 + (4-1) = 7 a1,a2,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=b1: next > position of b1 = 1*2=2 a1,b1,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and > temp=a2:next position of a2 = 2+(2-1)=3 > a1,b1,a2,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a3:next position of a3 = > 3+(3-1)=5 a1,b1,a2,b2,a3,a6,b4,b4,b3,b5,a6,b6 and temp=a5:next > position of a5 = 5+(5-1)=9 > a1,b1,a2,b2,a3,a6,b4,b4,a5,b5,a6,b6 and temp=b3:next position of b3 = > 3*2=6 > a1,b1,a2,b2,a3,b3,b4,b4,a5,b5,a6,b6 and temp=a6:next position of a6 = > 6 + (6-1)=11 > But now we find a6 already present at 11. Hence arranged in O(n) time > and constant space of 1 temp variable. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/2MD__54IXTkJ. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Navneet -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
