Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Storing and displaying numbers the indicies of number that appear 3+times in an array at O(n*logn) or better (http://www.velocityreviews.com/forums/t741255-storing-and-displaying-numbers-the-indicies-of-number-that-appear-3-times-in-an-array-at-o-n-logn-or-better.html)

 perditi0n2002 01-01-2011 11:29 PM

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

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

 Willem 01-01-2011 11:34 PM

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

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

 perditi0n2002 01-01-2011 11:41 PM

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

On Jan 2, 1:34*am, Willem <wil...@turtle.stack.nl> 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.

 perditi0n2002 01-02-2011 12:50 AM

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

On Jan 2, 1:34*am, Willem <wil...@turtle.stack.nl> 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?

 Willem 01-02-2011 08:31 AM

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

perditi0n2002 wrote:
) On Jan 2, 1:34?am, Willem <wil...@turtle.stack.nl> 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

 All times are GMT. The time now is 12:41 PM.