Btw this is just O(n) Algo as no of swaps are restricted to N-2
overall.
Kamlesh
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.
Hi all,
This is c code for the orginal problem.. I is working fine!
fuction(int a[], int N){
int swaps=0, i;
for(i=1;(i < N/2) && (swaps < N-2); i+=2)
{
int p=i, temp=a[i], inside=0, t;
while(p!=i || ! inside){
inside=1;
p= (p >= N/2) ? 2*p-N+1 : 2*p;
t=a[p]; a[p]=te
Whats the solution which you got in O(n log n)?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group
A similar approach
starting from an .. do shifts to place an, an-1 ... on their correct destinations
but when you come to pick displaced bn's (into a's half) back. you got to keep track of
2 positions at a's half.
this way you will finally get to the solution in o(n) time and o(1) space.
On 7/7/
Yet another approach. If instance size is n,
A B C D a b c d
1. swap the element at n/2 and n-1
A B C c a b D d
2. shift "a" and "b"
A B a b C c D d
Now the instance size is n/2 (A B a b) Recursively perform steps 1. and
2. on it.
The swaps are constant only the shifts are a function of n.
If the array is set that way specifically, you have the advantage on
knowing that b1 will always be at position n/2 + 1.
So you could do something like this:
idx1 = a1 (position 0)
idx2 = b1 (position n/2 + 1)
while idx1 < (n/2 + 1)
copy idx1 to new array
copy idx2 to new array
incremen
Arunachalam wrote:
> Hi,
> can you please elaborate on your question?
>
> If I understand you correct then you are given an array of Length 2n with
> elements a1,a2...an,b1,b2.. bn.
>
> Now you are asked to modify the array to a1,b1,a2,b2.an,bn.
>
> If this is the problem then the solutio
Arunachalam wrote:
> Hi,
> can you please elaborate on your question?
>
> If I understand you correct then you are given an array of Length 2n with
> elements a1,a2...an,b1,b2.. bn.
>
> Now you are asked to modify the array to a1,b1,a2,b2.an,bn.
>
> If this is the problem then the soluti
Hi,
for example consider this array
a1,a2,a3,b1,b2,b3.
Now you start with a2 which is not in its place. Mark the second place as empty move a2 to its position. Before moving make a copy of a3 in memory. Now put a2 there.
So the array will look like
a1,_,a2,b1,b2,b3. Now do the same thing
Hi dude,
it has only one more element to be moved in the extra space. Other elements use the existing array as the space so space complexity is O(1) clearly.
On 7/6/06, Vishal <[EMAIL PROTECTED]> wrote:
What about O(1) space complextity? I think your solution has space complexity of O(n).
hi arunachalam
i belv u got the question correct...but could u elaborate ur soln...
it s too handwavy..i still dont know how it can be done in place...
thanks
siva
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
What about O(1) space complextity? I think your solution has space complexity of O(n).~VishalOn 7/6/06, Arunachalam <
[EMAIL PROTECTED]> wrote:Hi,
can you please elaborate on your question?
If I understand you correct then you are given an array of Length 2n with elements a1,a2...an,b1,b2..
Hi,
can you please elaborate on your question?
If I understand you correct then you are given an array of Length 2n with elements a1,a2...an,b1,b2.. bn.
Now you are asked to modify the array to a1,b1,a2,b2.an,bn.
If this is the problem then the solution is straight forward. For each
13 matches
Mail list logo
