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
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
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!
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
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).
Hash tables fail the "extra space : constant" requirement.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
It won't do if the size of the input exceeds that amount.Originally Posted by EVOEx
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
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.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
@MK27: As I said, I expect there to be a constraint on the integers the OP didn't mention.
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.
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
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.Originally Posted by EVOEx
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
So is the problem not solvable in linear time!!! ???