harrypotter0's blog

By harrypotter0, history, 7 years ago, In English

Hello friends I cam across this problem

If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place

I came with an idea :: First swap elements in the middle pair

Next swap elements in the middle two pairs

Next swap elements in the middle three pairs

iterate n-1 steps.

Ex: with n = 4.

a1 a2 a3 a4 b1 b2 b3 b4

a1 a2 a3 b1 a4 b2 b3 b4

a1 a2 b1 a3 b2 a4 b3 b4

a1 b1 a2 b2 a3 b3 a4 b4

Can someone implement this in C++ . I know the problem asked is quite silly but I am not able to implement this using C++ . Somebody please help !!

OR

If anyone has a solution which takes O(n) time complexity and O(1) space complexity he/she is most welcome to add his code below in comments :-)

Space complexity of O(1) is the priority here . Thanks in advance :)

  • Vote: I like it
  • -18
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think a complexity less than O(N) is achievable since you have to remember all the ai values before starting to read the values of b.