Velocity Reviews > One algorithm problem

# One algorithm problem

mohangupta13
Guest
Posts: n/a

 04-18-2009
hello everyone , I don't know its the write place to ask this or not.
I have a problem and I am not able to get any algorithm for it.

Given two arrays A,B of size N , each with integers from 0-(N-1) . We
have to arrange the elements in array A as they are in B (by swapping
values) with the place in A holding the digit '0' used as the temp
variable for swapping , in O(n) time and WITHOUT using any extra
variable space.

example: A[]="3021"
B[]="2130"

output: A[]="2130" using position of '0' in A as temp variable
for swap.

questions if not here ( possibly any google groups?) ?

Thank you

Mohan Gupta

dfighter
Guest
Posts: n/a

 04-18-2009
mohangupta13 wrote:
> hello everyone , I don't know its the write place to ask this or not.
> I have a problem and I am not able to get any algorithm for it.
>
> Given two arrays A,B of size N , each with integers from 0-(N-1) . We
> have to arrange the elements in array A as they are in B (by swapping
> values) with the place in A holding the digit '0' used as the temp
> variable for swapping , in O(n) time and WITHOUT using any extra
> variable space.
>
> example: A[]="3021"
> B[]="2130"
>
> output: A[]="2130" using position of '0' in A as temp variable
> for swap.
>
>
> Also please provide any links where I can discuss algorithm related
> questions if not here ( possibly any google groups?) ?
>
>
> Thank you
>
> Mohan Gupta

Hi!
This group deals with "The C programming language", so I would say you
are at the wrong place.
You should probably try the comp.programming group.

Eric Sosman
Guest
Posts: n/a

 04-19-2009
blargg wrote:
> mohangupta13 wrote:
>> Given two arrays A,B of size N , each with integers from 0-(N-1) . We
>> have to arrange the elements in array A as they are in B (by swapping
>> values) with the place in A holding the digit '0' used as the temp
>> variable for swapping , in O(n) time and WITHOUT using any extra
>> variable space.
>>
>> example: A[]="3021"
>> B[]="2130"
>>
>> output: A[]="2130" using position of '0' in A as temp variable
>> for swap.

>
> void algo( int a[], int const b[], int N )
> {
> memcpy( a, b, N * sizeof a[0] );
> }
>
> memcpy shouldn't be using any temporary buffers related to N. What am I missing?

"By swapping values," I think, although he's not stating
his problem very clearly. In any event, he doesn't have a C
question (not yet, anyhow), and has already been referred to

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Andrew Tomazos
Guest
Posts: n/a

 04-20-2009
On Apr 18, 7:59*pm, mohangupta13 <(E-Mail Removed)> wrote:
> hello everyone , I don't know its the write place to ask this or not.
> I have a problem and I am not able to get any algorithm for it.
>
> Given two arrays A,B of size N , each with integers *from 0-(N-1) . We
> have to arrange the elements in array A as they are in B (by swapping
> values) with the place in A holding the digit '0' used as the temp
> variable for swapping , in O(n) time and WITHOUT using any extra
> variable space.
>
> example: *A[]="3021"
> * * * * * * * *B[]="2130"
>
> * * output: A[]="2130" * * using position of '0' in A as temp variable
> for swap.
>
> Also please provide any links where I can discuss algorithm related
> questions if not here ( possibly any google groups?) ?

Ive written and posted a C implementation here:

-Andrew.

CBFalconer
Guest
Posts: n/a

 04-20-2009
blargg wrote:
>

.... snip ...
>
> I miss the days when people posted URLs to actual messages, so
> they could be easily read with one's newsreader... here's a real
> URL to the message, rather than a portal:

Messages don't have URLs. A message mounted on google groups may
have an URL, but that has nothing to do with the message, which has
probably been mangled.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

Ben Bacarisse
Guest
Posts: n/a

 04-20-2009
CBFalconer <(E-Mail Removed)> writes:

> blargg wrote:
>>

> ... snip ...
>>
>> I miss the days when people posted URLs to actual messages, so
>> they could be easily read with one's newsreader... here's a real
>> URL to the message, rather than a portal:

I was going to thank you for this and then I thought such a message
would be noise, but since I am posting anyway: thanks, blargg.

> Messages don't have URLs.

Several RFCs beg to differ. The matter of what a message URL really
locates (and how) is, I agree, not clear-cut but the fact that
messages have URL is not really in doubt.

--
Ben.

Keith Thompson
Guest
Posts: n/a

 04-20-2009
CBFalconer <(E-Mail Removed)> writes:
> blargg wrote:
>>

> ... snip ...
>>
>> I miss the days when people posted URLs to actual messages, so
>> they could be easily read with one's newsreader... here's a real
>> URL to the message, rather than a portal:

>
> Messages don't have URLs. A message mounted on google groups may
> have an URL, but that has nothing to do with the message, which has
> probably been mangled.

You are mistaken. The portion of a URL preceding the ':' is called
the "scheme"; valid schemes include "http", "news", and "nntp".

The URL blargg posted:

<news:(E-Mail Removed)>

is both valid and correct (though it may actually be less useful than
a Google Groups URL, since you have to define the news server to use
it, and whatever server you're using might not have the article.)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

CBFalconer
Guest
Posts: n/a

 04-21-2009
Keith Thompson wrote:
> CBFalconer <(E-Mail Removed)> writes:
>

.... snip ...
>
>> Messages don't have URLs. A message mounted on google groups may
>> have an URL, but that has nothing to do with the message, which has
>> probably been mangled.

>
> You are mistaken. The portion of a URL preceding the ':' is called
> the "scheme"; valid schemes include "http", "news", and "nntp".
>
> The URL blargg posted:
>
> <news:(E-Mail Removed)>
>
> is both valid and correct (though it may actually be less useful than
> a Google Groups URL, since you have to define the news server to use
> it, and whatever server you're using might not have the article.)

Thanks. I learned something new.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>