# Thread: Elements repeated thrice except one

1. I tried to solve it using XOR approach, from where I could not conclude anything fruitful.
If you can't figure out how to do this with the simple `XOR' approach, it is because you have a broken implementation or didn't implement the logic correctly, but you seem to have the right idea. If you post what you have, instead of just saying you've tried what you know, I imagine that you'll get pointed in the right direction.

Soma 2. Originally Posted by anirban Also, I cannot apply sorting as O(nlogn) would be necessary.
So what? It's only necessary as a prerequisite for a simple linear algorithm. Or, thinking about thinking, would you say binary search doesn't work in O(logn) time because it requires the array to be sorted, too? See, I think you're making this harder than it needs to be. 3. Originally Posted by brewbuck Take every number in the array and remove all factors of three, by repeatedly dividing by three until the result is no longer divisible by three.

Sum the elements of the array. Because each element is repeated three times, except for one of them, this sum will be of the form:

Sum = 3*(x1+x2+..)+xk

Where xk is the element you are looking for.

Now, because xk is not divisible by three (you already removed all factors of three from the elements), the sum is not divisible by three...
S = 3*(x1+x2+..)+xk

and we want to find k.

Loop through the array again but subtract 3*xi from S
if i != k then (S-3*xi)%3 == xk
if i == k then (S-3*xi)%3 == -2*xk

So, in the first iteration we get either r1 = xk or -2*xk.
At a later iteration, j, we'll get r2 equal the other one.
If r1/r2 == 0, then k=j, otherwise k=0.

Edit: On second thought, this is wrong. I had misunderstood what you meant by "removing factors of three". 4. Originally Posted by whiteflags So what? It's only necessary as a prerequisite for a simple linear algorithm. Or, thinking about thinking, would you say binary search doesn't work in O(logn) time because it requires the array to be sorted, too? See, I think you're making this harder than it needs to be.
Nowhere in the problem description did it say the numbers were already sorted. If you are given a million elements and have to write an algorithm that finishes within one second on a test machine, you can't do a O(n^2) "preparation" even if you think it's not the most interesting part of the algorithm.

And yes, one single binary search on an unsorted array has O(nlogn) complexity. But you only use binary search if you have to perform it some n times on a given set of data. 5. Originally Posted by maxorator
Nowhere in the problem description did it say the numbers were already sorted. If you are given a million elements and have to write an algorithm that finishes within one second on a test machine, you can't do a O(n^2) "preparation" even if you think it's not the most interesting part of the algorithm.
You mean in your opinion I can't. Of course I can. Nowhere in the problem description did it say that I had to complete the task in a second.
And yes, one single binary search on an unsorted array has O(nlogn) complexity. But you only use binary search if you have to perform it some n times on a given set of data.
On unsorted data, binary search doesn't even work, so I don't understand what you're saying. 6. Originally Posted by lattica Edit: On second thought, this is wrong. I had misunderstood what you meant by "removing factors of three".
Yeah, but I think you're on the right track with the idea of making two passes with two kinds of checks, sandwiching the answer in between somehow. 7. Originally Posted by whiteflags You mean in your opinion I can't. Of course I can. Nowhere in the problem description did it say that I had to complete the task in a second.
Obviously I was talking about a hypothetical task. In this case the restriction is O(n) time, in which the unsorted array must be processed. The O(n) restriction starts when you receive input and ends when you output the result, since algorithm by definition means processing input data to output the result in the desired format. Sorting the data takes place obviously between those two moments. Originally Posted by whiteflags On unsorted data, binary search doesn't even work, so I don't understand what you're saying.
Let me rephrase it: an algorithm that takes unsorted data as input and performs a search on it using the binary search algorithm in the process takes O(nlogn) time. But of course you already knew what I meant. 8. Originally Posted by maxorator Obviously I was talking about a hypothetical task. In this case the restriction is O(n) time, in which the unsorted array must be processed. The O(n) restriction starts when you receive input and ends when you output the result, since algorithm by definition means processing input data to output the result in the desired format. Sorting the data takes place obviously between those two moments.
I'm sorry? This is what I read: Originally Posted by anirban There is an array of N elements. All but one is repeated thrice. That element has occurred only once. Find the element in O(N) time.
The key wording being here. You're communicating to me that the entire program must run in O(n) time, which really does not make sense. I don't get the same sense of restriction that you do. Sorting things will never find an element. In what sense it could be construed as part of the algorithm is only because it is a requirement that the simplest O(n) algorithm will need to work on sorted input. And if the input in any case is a sorted array, then I don't see a problem. You're styling yourself as a master of the facts here and I don't understand your sense of conviction that I'm wrong. 9. Originally Posted by maxorator The O(n) restriction starts when you receive input and ends when you output the result
Let's assume so, yes.

But...
Sorting the data takes place obviously between those two moments.
Well, no. For that to be true, the question would have to make mention to the state of the data. That is, for the sorting operation -- should you wish to include one -- to be accounted for, the question would have be explicit in that the data is unsorted.

Instead there's no reference to the state of the data, so anything goes. You are only given information about the input. In this case, should you wish to sort the array because your method involves sorting, you may happily turn that into a pre-requisite of your algorithm instead of including it.

I just want to stress this out: In problem solving, both data state and input must be referenced. If one of them isn't, it automatically ceases to be a requirement and you are free to include a pre-requisite without any penalty. 10. Originally Posted by anirban There is an array of N elements. All but one is repeated thrice. That element has occurred only once. Find the element in O(N) time.
It seems like the simplest solution would be to just use a hash table of int -> int that maps A[i] to an occurrence count on a first iteration of the array.

On the second sweep through find the key,value pair whose value is 1. The key will be the element that has one occurrence.

I believe this will be O(2n) = O(n). Assuming a well designed hash table. 11. If the repetition is even times, the unique element could be found in O(N) time simply by XORing all elements in the array. 12. Originally Posted by Mario F. Well, no. For that to be true, the question would have to make mention to the state of the data. That is, for the sorting operation -- should you wish to include one -- to be accounted for, the question would have be explicit in that the data is unsorted.
You cannot assume the data to be sorted unless it is explicitly said so. In fact you can't assume anything about input data that is not given in the text. I personally have never seen a programming task where it is explicitly said that the input data is unsorted. Therefore it can be either sorted or unsorted, which makes the worst case complexity at least O(nlogn) (since it takes O(n) to check if it's sorted and if it isn't, it takes O(nlogn) to sort it) - that is if you need the data to be sorted. 13. I didn't say anything about assumptions. Nothing is assumed. I suggest you read again.

There's a vast difference between asking to write an algorithm taking a unsorted array as an input, and asking to write an algorithm that takes an array as an input. The latter does not cite the state of the data before the algorithm is applied, so the algorithm can -- and this is actually desirable if there is a need to sort -- request the system to do the sorting itself by forcing the sorting as a pre-requisite. This is the nature of many known algorithms, maxorator. All this is news at 11.

And it is actually desirable for such an algorithm to not perform a sort, because a sort alters the state and this is usually something that search algorithms should avoid. The alternative would be for it to perform the sort on a new array, increasing the space requirements of the algorithm... often to unacceptable levels.

You need to reevaluate this position of yours. You are not only technically mistaken, but also, following your logic, you are bound to produce inefficient algorithms. 14. Originally Posted by Mario F. You need to reevaluate this position of yours. You are not only technically mistaken, but also, following your logic, you are bound to produce inefficient algorithms.
I'm talking about situations where you are given some input and you have no way to affect how the input comes, your code just has to complete the task at hand. Therefore, if you have an input file that has an array of data and it is not said that it is sorted and the core algorithm to reach the desired output requires a sorted set of data, your code has to do the sorting. It cannot force the system to do anything because there is no system - there is just raw data and it's not sorted. If you are given a task, you don't make the rules, you can't force the input to come differently, you can't abort because the data is not in the format that you like. 15. Originally Posted by maxorator Therefore, if you have an input file that has an array of data and it is not said that it is sorted and the core algorithm to reach the desired output requires a sorted set of data, your code has to do the sorting.
No. It hasn't. That's what we are trying to tell you. I have no idea how I can convince you of this more than I have. I suspect we will be going around in circles if I have to start repeating my arguments.

But in any case, even if that was a requirement of this particular problem, the immediate answer to the OP was that there was no solution for this exercise. As soon as you make sort an integral part of this algorithm, this problem cannot be solved in O(N), unless you are willing to consider only best cases... which I will object strongly.

It cannot force the system to do anything because there is no system - there is just raw data and it's not sorted.
There is always a "system". An algorithm doesn't exist in the vaccum. The system holds the data and the state. The algorithm processes the data, alters or not the state and produces or not an output.

If you are given a task, you don't make the rules, you can't force the input to come differently, you can't abort because the data is not in the format that you like.
At this point I'm not sure what you are talking about. No one is changing rules here. In fact this debate happens because you are trying to introduce a new rule where previously there was none -- And your rule is, an algorithm that requires sorting needs to make the sort a part of its complexity description.

I suggest that if you want to negate binary search it's current O(logn) status, write a paper about it and present your case with better argumentation than what you did here. Because you'll have a lot of explaining to do to the scientific and computer communities. Popular pages Recent additions 