Thread: Number repeated thrice

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Number repeated thrice

    Given an array of integers where some numbers do not repeat, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times

    Time complexity : O(n)
    Extra space : Constant

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Right. Show us your effort first. We will not do your homework.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Actually I have succeed in solving a problem similar to this but could not crack this!
    This is not homework. I tried solving this using XOR. But failed!

    If any idea, then please post!

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Create a hash table, using each number as a key, and increment the value for each occurrence.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    Create a hash table, using each number as a key, and increment the value for each occurrence.
    Unless the hash table has a unique element per number, it works. However, if there are no constraints on the numbers, it may require one hell of a table. If it has one element for several numbers then it's not O(n) complexity.

    But AFAIK there's no O(n) complexity without using a "hash table" (I don't really consider this a hash table as it's just a plain array where the number is the index and no real hashing is done, but that might be my definition being off).

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Hash tables fail the "extra space : constant" requirement.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by brewbuck View Post
    Hash tables fail the "extra space : constant" requirement.
    Not if there's a constraint on the numbers. Eg. if only numbers 0-100 appear... Which I expect is the case, but he failed to mention this critical fact.

    And by the way, a hash table with 2^32 elements is still constant...

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by EVOEx
    And by the way, a hash table with 2^32 elements is still constant...
    It won't do if the size of the input exceeds that amount.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by EVOEx View Post
    However, if there are no constraints on the numbers, it may require one hell of a table.
    The size of the table would equal the number of (unique) numbers, so it would only be a "hell of a table" if it was already a "hell of an array". It certainly will be way smaller than using a straight array index, if the array was "2, 12312335, 35, 79" -- that's a four element hash table or a 12312335 element array index.

    However, I didn't notice the "extra space = constant thing", if this means use no storage beyond the array itself, tricky indeed.

    If it just means the extra storage must be of constant size, well, just make a pool of nodes equal to the number of elements in the array, and that will cover the table.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by MK27
    However, I didn't notice the "extra space = constant thing", if this means use no storage beyond the array itself, tricky indeed.
    It usually means that you are allowed some extra space, but this is a fixed amount, i.e., it does not vary with the size of the input. Consequently, "a pool of nodes equal to the number of elements in the array" is not a constant amount of (extra) space.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    @MK27: As I said, I expect there to be a constraint on the integers the OP didn't mention.

    Quote Originally Posted by laserlight View Post
    It won't do if the size of the input exceeds that amount.
    Well, I think integers are defined to have a minimum/maximum. In that case, you can use this minimum and maximum to calculate the required size of the table. Meaning it would be constant throughout the same architecture. Of course, it would require several gigabytes of memory at least.
    Of course, it's completely infeasible. But without constraints to the numbers I'm quite sure this assignment can't be done in O(n) in any other way.

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    It usually means that you are allowed some extra space, but this is a fixed amount, i.e., it does not vary with the size of the input. Consequently, "a pool of nodes equal to the number of elements in the array" is not a constant amount of (extra) space.
    Okay, I follow. So the parallel array is also out. Looks hard.

    Here's a tentative idea: Go thru the array and eliminate all the elements that do not equal another element. Now, eliminate one of each of those and do the same thing.

    The only elements which remain matching another element would be ones which occurred three times initially. This requires no extra space, but it is way more than O(n)....I give up
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by EVOEx
    Well, I think integers are defined to have a minimum/maximum. In that case, you can use this minimum and maximum to calculate the required size of the table. Meaning it would be constant throughout the same architecture.
    This is not the usual definition of constant space complexity. There is the possibility of arbitrary precision arithmetic, but then this would also affect the time and space complexity. I think that it would be better to just check to see if your guess of a missing requirement is correct.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by MK27 View Post
    Here's a tentative idea: Go thru the array and eliminate all the elements that do not equal another element. Now, eliminate one of each of those and do the same thing.

    The only elements which remain matching another element would be ones which occurred three times initially. This requires no extra space, but it is way more than O(n)....I give up
    Nope, that's O(n^2).

    @laserlight:
    I know that's not the usual definition of constant space complexity. But it was kind of a sarcastic as, as I said, there is no solution to this. I've googled around for this, and everything agreed with my earlier expectation. You need at least one bit for every possible integer to solve this in O(n). Probably even more though.

  15. #15
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    So is the problem not solvable in linear time!!! ???

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Guess My Number (Need help)
    By dhardin in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2009, 12:59 PM
  2. Need help with this compiler error
    By Evangeline in forum C Programming
    Replies: 7
    Last Post: 04-05-2008, 09:27 AM
  3. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM
  4. help with a source code..
    By venom424 in forum C++ Programming
    Replies: 8
    Last Post: 05-21-2004, 12:42 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM