Guys 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
Observation: 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 Thanks, Sourav Sain On Jun 9, 8:54 pm, Anurag Sharma <anuragvic...@gmail.com> wrote: > Its not O(n) time. > > Anurag Sharma > > On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha > <jitendra.th...@gmail.com>wrote: > > > > > here is a sel explainatory algo > > > given: > > > abcd1234 > > abc1d234 > > ab1c2d34 > > a1b2c3d4 > > > here is the link for the code :http://codepad.org/SZnufGc6 > > > -- > > Regards > > Jitendra Kushwaha > > MNNIT, Allahabad > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
