Author |
Topic: rearrange the array. (Read 6468 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Re: rearrange the array.
« Reply #25 on: Apr 9th, 2008, 10:25am » |
 Quote  Modify
|
Aakash, did you read the algo that was posted?
It is O(n) time and O(log n) bit space, so it is minimum in terms of time and space complexity.
O(n) bits is not mimimum space... as we can do better (O(logn) bits).
So the statement, "... we _need_ a bit array of size n ..." is misleading.
|
|
 IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: rearrange the array.
« Reply #26 on: Apr 9th, 2008, 10:37am » |
Quote Modify
|
i did..
no doubt it is better in terms of space complexity...
whatever i have given is best only if the data is positive.
one more positive side of algorithm i have given is its simplicity.
i edited that post as per your suggestion
|
| « Last Edit: Apr 9th, 2008, 10:42am by m_aakash » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #27 on: Apr 9th, 2008, 5:26pm » |
Quote Modify
|
Well if you are willing to trade on space for simplicity, why not just create another array and put the elements in their right place? O(nlogn) space, but really simple algorithm.
I think you are missing the spirit of the puzzle. And if not, I apologize and won't say anything further.
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: rearrange the array.
« Reply #28 on: Apr 10th, 2008, 12:32am » |
Quote Modify
|
on Apr 9th, 2008, 5:26pm, Aryabhatta wrote:Well if you are willing to trade on space for simplicity, why not just create another array and put the elements in their right place? O(nlogn) space, but really simple algorithm.
|
|
If you create other array it will take O(n) element space. but we only need O(n) bit space to implement my algorithm. it is certainly better. The needed logic is what i have given in my algorithm. If the elements are positive even we dont need that O(n) bit space.
Quote:
I think you are missing the spirit of the puzzle. And if not, I apologize and won't say anything further.
|
|
one insight to the puzzle is what i presented that is definitely not trivial.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: rearrange the array.
« Reply #29 on: Apr 10th, 2008, 9:23am » |
Quote Modify
|
on Apr 10th, 2008, 12:32am, m_aakash wrote:
If you create other array it will take O(n) element space. but we only need O(n) bit space to implement my algorithm. it is certainly better. The needed logic is what i have given in my algorithm. If the elements are positive even we dont need that O(n) bit space.
|
|
You don't need O(n) element space. O(nlogn) bit space is enough. (You can store the indices and not the elements themselves).
Anyway, I think there is no point discussing this further.
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: rearrange the array.
« Reply #30 on: Apr 10th, 2008, 10:05am » |
Quote Modify
|
yes..O(nlogn) bit space is sufficient but it still more than O(n) bit space.
i feel it needs attention because this idea is used for transposing rectangular array inplace as well. This puzzle is just a special case of transposing 2*n array.
|
| « Last Edit: Apr 10th, 2008, 10:09am by m_aakash » |
IP Logged |
|
|
|
Devil
Newbie
Gender:
Posts: 1
|
|
Re: rearrange the array.
« Reply #31 on: Apr 12th, 2008, 8:53pm » |
Quote Modify
|
my shot at it
2n = no of items
for(i = 0; i < n - 1; i++)
{
y = x[n + i];
for(j = n + i; j > (2 * i + 1); j--)
{
x[j] = x [j - 1];
}
x[2 * i + 1] = y;
}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: rearrange the array.
« Reply #32 on: Apr 13th, 2008, 12:47pm » |
Quote Modify
|
That is O(n2)
|
|
IP Logged |
|
|
|
game_iiith
Newbie
Posts: 5
|
|
Re: rearrange the array.
« Reply #33 on: Nov 24th, 2009, 10:01pm » |
Quote Modify
|
My try at the problem, but I feel its too trivial looking at the discussion which this problem has aroused. Can somebody please point out an error in my understanding/algorithm of the problem.
Code:
#include <stdio.h>
int main()
{
int n, i, j , k, t1, l;
scanf("%d",&n);
int arr[n<<1+1];
for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ )
{
if ( i <= n )
arr[i] = k+=2; // 1 3 5 7
else
arr[i] = l+=2;
}
arr[0]=0;
// Shuffleing starts
i = 1;
int chk[j+1]; // To check if each element was visited only once
for (i=0;i<=j;i++)chk[i]=0;
i = 1;
while (i <= j)
{
while (i<=j && arr[i] == i) i++;
if (i >j)
break;
t1 = arr[i]; // swap with temp
k = i; // note the curr. loc in array
l = i;
printf("%d : Value of i entering loop\n",i);
while (1)
{
k = k&1?(k+1)/2:n+k/2;
chk[k]++;
if ( k == i)
break;
arr[l] = arr[k];
l = k;
}
arr[l] = t1;
}
for (i=0;i<=j;i++)
printf("%d ",arr[i]);
printf("\n");
for (i=0;i<=j;i++)
if (chk[i]>1)
printf("%d %d\n",i,chk[i]);
return 0;
}
|
|
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: rearrange the array.
« Reply #34 on: Feb 7th, 2010, 9:24am » |
Quote Modify
|
Aryabhatta, i went through the link where you have posted the problem. I read the entire paper you wrote. I personally feel the algorithm you have presented has a sound proof w.r.t Mathematical Analysis. One thing i want to say, in your paper you have nowhere talkes about the space complexity - although a header seems to be there. Although i read grimbals post where he insited on the fact that the space complexity would be O(logn). I am still not getting how can we claim it. i will read the posts once again to work on the space complexity part. Thanks.
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: rearrange the array.
« Reply #35 on: Feb 7th, 2010, 9:38am » |
Quote Modify
|
Additionaly, towr could you help me with this.
I read the O(nlogn) solution in one of the posts.
Call Rearrange(A,1,2N) initially, it will rearrange the array in O(1) space. The time complexity is discussed at the end.
Rearrange(A,p,q)
1. if p is not equal to q do the following
2. r ←- (p+q)/2
3. Exchange A[(p+r)/2..r] ←→ A[(p+q)/2 +1 ..(r+q)/2].
4. Rearrange(A,p,r)
5. Rearrange(A,r+1,q)
6. return
I have doubts about step3. Can someone throw light on this.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: rearrange the array.
« Reply #36 on: Feb 7th, 2010, 10:05am » |
Quote Modify
|
on Feb 7th, 2010, 9:38am, hary wrote:| I have doubts about step3. Can someone throw light on this. |
|
What that algorithm does is to ensure that each subarray you work with in later steps has some number of A's followed by the same number of Bs: {Ai, Ai+1, .., Aj, Bi, Bi+1, .., Bj}
So it goes
A1, A2, A3, A4, A5, A6, A7, B1, B2, B3, B4, B5, B6, B7
A1, A2, A3, A4, B1, B2, B3, B4, A5, A6, A7, B5, B6, B7
A1, A2, B1, B2, A3, A4, B3, B4, A5, A6, B5, B6, A7, B7
A1, B1, A2, B2, A3, B3, A4, B4, A5, B5, A6, B6, A7, B7
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: rearrange the array.
« Reply #37 on: Feb 8th, 2010, 7:14pm » |
Quote Modify
|
Try this.
A1 B1
Nothing to be done
A1 A2 B1 B2
Start at n/2+1 = 3 position i.e B1 and move it one element backward. Now A2, moves 1 element forward, if A3 exists it moves one element forward etc..
A1 A2 A3 B1 B2 B3
-> A1 B1 A2 B2 A2 B3
A1 A2 A3 A4 B1 B2 B3 B4
-> A1 B1 A2 B2 A3 B3 A4 B4
The idea is as below.
Start from n+1 to 2n.
Move the A2, 1 point, A3, 2 points forward etc..
If you cannot find a position to put an element, start from N+1 and move them back filling in the spaces.
This takes minimum number of steps.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print