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. 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
    #1
    1. Advertising

  2. perditi0n2002

    Willem Guest

    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
    #2
    1. Advertising

  3. 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
    #3
  4. 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
    #4
  5. perditi0n2002

    Willem Guest

    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
    #5
    1. Advertising

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.
Similar Threads
  1. Roy Chastain
    Replies:
    2
    Views:
    431
    Sunwest Technologies
    Jun 1, 2004
  2. guoqi zheng

    too logn viewstate

    guoqi zheng, May 6, 2005, in forum: ASP .Net
    Replies:
    8
    Views:
    402
    Aquila Deus
    May 8, 2005
  3. Phrogz
    Replies:
    8
    Views:
    277
    Morton Goldberg
    Feb 8, 2007
  4. Replies:
    72
    Views:
    767
    88888 Dihedral
    Nov 2, 2012
  5. Andrew Robinson

    Re: Negative array indicies and slice()

    Andrew Robinson, Oct 29, 2012, in forum: Python
    Replies:
    0
    Views:
    122
    Andrew Robinson
    Oct 29, 2012
Loading...

Share This Page