Author |
Topic: Array Building (Read 812 times) |
|
mad
Junior Member
Posts: 118
|
 |
Array Building
« on: Feb 27th, 2008, 8:46pm » |
 Quote  Modify
|
Given two arrays X and Y , we are required to build an array Z from them st. elements in Y are either 0,1,or -1. If Y[i] is 0,Z[i]=X[i].
Else if Y[i]=-1, X[i] lies somewhere between indices 0 and i-1 in Z[i].
Else, X[i] lies inbetween i+1 and n-1 where n is length of both arrays.
|
|
 IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Array Building
« Reply #1 on: Mar 2nd, 2008, 8:33pm » |
Quote Modify
|
I can think of doing it in O(n) time using O(n) extra space maintaining 2 queues to store the indices of empty spaces in Z[] where the elements corresponding to Y[] can be stored.
Can it be done better?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Array Building
« Reply #2 on: Mar 3rd, 2008, 1:25am » |
Quote Modify
|
I think you do it without extra space in O(n) time.
use three passes
Of course it may be impossible in some cases to start with
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Array Building
« Reply #3 on: Mar 3rd, 2008, 3:45am » |
Quote Modify
|
In some cases, there are more than one solution.
One solution:
Normally, the first non-zero Y[i] should be +1. The last one should be -1.
So, shift right all the X[i] where Y[i]=+1, (i.e. to the next position with Y[i]=+1), move the last X[i] with Y[i]=+1 to the last i where Y[i]=-1, shift left all the X[i] where Y[i]=-1 to the next -1 and the last one to the first position where Y[i]=+1. It should take 2 passes.
edit: typo
|
| « Last Edit: Mar 20th, 2008, 5:35am by Grimbal » |
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Array Building
« Reply #4 on: Mar 20th, 2008, 5:23am » |
Quote Modify
|
@Grimbal
Solution proposed by you is not working for the following example, can u clear my doubt?
Input
A : 1 2 4 5 7 8
B : 0 1 0 -1 1 -1
Ans : 1 5 4 2 8 7
Ur Solution Answer : 1 5 4 8 2 7
Correct me if I am wrong....
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array Building
« Reply #5 on: Mar 20th, 2008, 5:36am » |
Quote Modify
|
on Mar 20th, 2008, 5:23am, johny_cage wrote:Solution proposed by you is not working for the following example, can u clear my doubt?
Input
A : 1 2 4 5 7 8
B : 0 1 0 -1 1 -1
Ans : 1 5 4 2 8 7
Ur Solution Answer : 1 5 4 8 2 7 |
|
Why wouldn't 1 5 4 8 2 7 be a solution? 1 and 4 are in their original place, 2,7 are to the right of their original position, 5,8 are to the left of their original position. What else can you want?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Array Building
« Reply #6 on: Mar 20th, 2008, 5:40am » |
Quote Modify
|
It is the case where there is more than one solution. Doesn't my solution match the requirements?
For example, with
X: 1 2 3 4
Y: +1 +1 -1 -1
you have 5 solutions
Z: 3 1 4 2
Z: 3 4 1 2
Z: 4 3 1 2
Z: 3 4 2 1
Z: 4 3 2 1
|
| « Last Edit: Mar 20th, 2008, 5:47am by Grimbal » |
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Array Building
« Reply #7 on: Mar 20th, 2008, 6:01am » |
Quote Modify
|
@Towr
That means I am still confused with the question. Because as per my understanding of the question the output array must be consistent w.r.t. array B. So, w.r.t 8 in Grimbal's output, array B contains -1, that is 8 must be on left side now, but it is on right side in A.
If I am wrong, then please explain me the question again....
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Array Building
« Reply #8 on: Mar 20th, 2008, 6:02am » |
Quote Modify
|
@Grimbal,
I think your solution is not matching the requirements as I already wrote in above post for towr the problem with number 8.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Array Building
« Reply #9 on: Mar 20th, 2008, 7:36am » |
Quote Modify
|
on Mar 20th, 2008, 6:01am, johny_cage wrote:That means I am still confused with the question. Because as per my understanding of the question the output array must be consistent w.r.t. array B. So, w.r.t 8 in Grimbal's output, array B contains -1, that is 8 must be on left side now, but it is on right side in A.
If I am wrong, then please explain me the question again.... |
|
The way I read it, the question is:
Given X and Y, find a Z, such that
Y[i]=0 <=> Z[i]=X[i]
Y[i]=-1 <=>  j 0  j < i: Z[j]=X[i]
Y[i]=1 <=> j i < j n: Z[j]=X[i]
(switching from Z[j]=X[i] to Z[i]=X[j] in the last two clauses seems to correspond with what you're doing)
|
| « Last Edit: Mar 20th, 2008, 7:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Array Building
« Reply #10 on: Mar 20th, 2008, 10:52am » |
Quote Modify
|
do we have to display all soln.s in the case where more than 1 is possible....
|
| « Last Edit: Mar 20th, 2008, 10:52am by pscoe2 » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Array Building
« Reply #11 on: Mar 20th, 2008, 5:44pm » |
Quote Modify
|
on Mar 20th, 2008, 6:02am, johny_cage wrote:@Grimbal,
I think your solution is not matching the requirements as I already wrote in above post for towr the problem with number 8. |
|
Same answer as towr's answer. It seems to me the array with +1/0/-1 refers to the 1st array, not the answer array. The -1 as 4th element of B in your example refers to the 5 in array A, so there must be a 5 before the 4th position in the answer.
If you do it the other way round, you just need to reverse the permutation I described, which gives (1 7 4 2 8 5).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print