1. ## 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. Right. Show us your effort first. We will not do your homework.

3. 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. Create a hash table, using each number as a key, and increment the value for each occurrence.

5. Originally Posted by MK27
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. Hash tables fail the "extra space : constant" requirement.

7. Originally Posted by brewbuck
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. 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.

9. Originally Posted by EVOEx
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.

10. 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.

11. @MK27: As I said, I expect there to be a constraint on the integers the OP didn't mention.

Originally Posted by laserlight
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. Originally Posted by laserlight
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

13. 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.

14. Originally Posted by MK27
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. So is the problem not solvable in linear time!!! ???