nice algo! Anurag Sharma
On Wed, Jun 9, 2010 at 11:23 PM, souravsain <souravs...@gmail.com> wrote: > 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> > <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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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.
