«

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

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

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.

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?

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