- **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*)

Storing and displaying numbers the indicies of number that appear 3+times in an array at O(n*logn) or betterHi 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 |

Re: Storing and displaying numbers the indicies of number thatappear 3+ times in an array at O(n*logn) or betterperditi0n2002 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 |

Re: Storing and displaying numbers the indicies of number that appear3+ times in an array at O(n*logn) or betterOn 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. |

Re: Storing and displaying numbers the indicies of number that appear3+ times in an array at O(n*logn) or betterOn 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? |

Re: Storing and displaying numbers the indicies of number thatappear 3+ times in an array at O(n*logn) or betterperditi0n2002 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. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.