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

Discussion in 'C Programming' started by perditi0n2002, Jan 1, 2011.

1. ### perditi0n2002Guest

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, Jan 1, 2011

2. ### WillemGuest

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
Willem, Jan 1, 2011

3. ### perditi0n2002Guest

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 <> 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, Jan 1, 2011
4. ### perditi0n2002Guest

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 <> 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, Jan 2, 2011
5. ### WillemGuest

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 <> 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
Willem, Jan 2, 2011

### Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.