Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Storing and displaying numbers the indicies of number that appear 3+times in an array at O(n*logn) or better

Reply
Thread Tools

Storing and displaying numbers the indicies of number that appear 3+times in an array at O(n*logn) or better

 
 
perditi0n2002
Guest
Posts: n/a
 
      01-01-2011
Hi everyone
I was given a question that takes a sorted array (well it was unsorted
but I merge sorted it to simplify the problem) and you must return the
indicies of numbers which appear 3 or more times in the array, at
O(n*logn) or less complexity.
This doesn't seem too plausible to me since even if I were to go over
the array and make a 2d array of [distinct numbers which appear 3+
times][n] it would still take me more than n times to go over the
original array and store the indicies.
Does anyone have any clue how this is possible?

an example of the program:
array: 2 3 4 2 2 5 2 4 3 4 2

output:
2: 0,3,4,6,10
4:2,7,9
 
Reply With Quote
 
 
 
 
Willem
Guest
Posts: n/a
 
      01-01-2011
perditi0n2002 wrote:
) Hi everyone
) I was given a question that takes a sorted array (well it was unsorted
) but I merge sorted it to simplify the problem) and you must return the
) indicies of numbers which appear 3 or more times in the array, at
) O(n*logn) or less complexity.
) This doesn't seem too plausible to me since even if I were to go over
) the array and make a 2d array of [distinct numbers which appear 3+
) times][n] it would still take me more than n times to go over the
) original array and store the indicies.
) Does anyone have any clue how this is possible?

How much extra memory are you allowed to use ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
Reply With Quote
 
 
 
 
perditi0n2002
Guest
Posts: n/a
 
      01-01-2011
On Jan 2, 1:34*am, Willem <(E-Mail Removed)> wrote:
> perditi0n2002 wrote:
>
> ) Hi everyone
> ) I was given a question that takes a sorted array (well it was unsorted
> ) but I merge sorted it to simplify the problem) and you must return the
> ) indicies of numbers which appear 3 or more times in the array, at
> ) O(n*logn) or less complexity.
> ) This doesn't seem too plausible to me since even if I were to go over
> ) the array and make a 2d array of [distinct numbers which appear 3+
> ) times][n] it would still take me more than n times to go over the
> ) original array and store the indicies.
> ) Does anyone have any clue how this is possible?
>
> How much extra memory are you allowed to use ?
>
> SaSW, Willem
> --
> Disclaimer: I am in no way responsible for any of the statements
> * * * * * * made in the above text. For all I know I might be
> * * * * * * drugged or something..
> * * * * * * No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT


No restriction specified, but using a naive bucket sort would
naturally be overkill since it can be any positive integer.
 
Reply With Quote
 
perditi0n2002
Guest
Posts: n/a
 
      01-02-2011
On Jan 2, 1:34*am, Willem <(E-Mail Removed)> wrote:
> perditi0n2002 wrote:
>
> ) Hi everyone
> ) I was given a question that takes a sorted array (well it was unsorted
> ) but I merge sorted it to simplify the problem) and you must return the
> ) indicies of numbers which appear 3 or more times in the array, at
> ) O(n*logn) or less complexity.
> ) This doesn't seem too plausible to me since even if I were to go over
> ) the array and make a 2d array of [distinct numbers which appear 3+
> ) times][n] it would still take me more than n times to go over the
> ) original array and store the indicies.
> ) Does anyone have any clue how this is possible?
>
> How much extra memory are you allowed to use ?
>
> SaSW, Willem
> --
> Disclaimer: I am in no way responsible for any of the statements
> * * * * * * made in the above text. For all I know I might be
> * * * * * * drugged or something..
> * * * * * * No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT


Any thoughts?
 
Reply With Quote
 
Willem
Guest
Posts: n/a
 
      01-02-2011
perditi0n2002 wrote:
) On Jan 2, 1:34?am, Willem <(E-Mail Removed)> wrote:
)> perditi0n2002 wrote:
)>
)> ) Hi everyone
)> ) I was given a question that takes a sorted array (well it was unsorted
)> ) but I merge sorted it to simplify the problem) and you must return the
)> ) indicies of numbers which appear 3 or more times in the array, at
)> ) O(n*logn) or less complexity.
)> ) This doesn't seem too plausible to me since even if I were to go over
)> ) the array and make a 2d array of [distinct numbers which appear 3+
)> ) times][n] it would still take me more than n times to go over the
)> ) original array and store the indicies.
)> ) Does anyone have any clue how this is possible?
)>
)> How much extra memory are you allowed to use ?
)
) No restriction specified, but using a naive bucket sort would
) naturally be overkill since it can be any positive integer.

You can store other things besides buckets.
And you only need O(n) extra memory: One thing per original entry.
(Some pedants might point out it's O(n lg n), but that's debatable.)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
problem in running a basic code in python 3.3.0 that includes HTML file Satabdi Mukherjee Python 1 04-04-2013 07:48 PM
Negative array indicies and slice() andrewr3mail@gmail.com Python 72 11-02-2012 01:08 AM
Re: Negative array indicies and slice() Ethan Furman Python 0 10-30-2012 09:21 PM
Re: Negative array indicies and slice() Mark Lawrence Python 0 10-29-2012 10:10 AM
Re: Negative array indicies and slice() Andrew Robinson Python 0 10-29-2012 02:31 AM



Advertisments