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.
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.
I found it in O(1) time.
Do you have any ideas, apart from just dumping your assignment on us?
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I have few questions.Originally Posted by Salem
1. Firstly, how do you define a homework question? Do you mean those questions which you cannot answer or do not want to share answer?
2. Secondly, if I cannot solve a problem what is the harm in discussing in an open forum? It is not about giving up, it is about sharing concepts. Any issues on this "IDEA"?
Personally in forums I do not post unusual replies instead of helping and I would also like the same rule to be applied in case of my post. If you do not have answer/do not want to help, ZIP/RAR your lips.Isn't it a great "idea"?
By what possible stretch of rules do you think it is appropriate to come in here making demands?I have few questions.
1. Firstly, how do you define a homework question? Do you mean those questions which you cannot answer or do not want to share answer?
2. Secondly, if I cannot solve a problem what is the harm in discussing in an open forum? It is not about giving up, it is about sharing concepts. Any issues on this "IDEA"?
Personally in forums I do not post unusual replies instead of helping and I would also like the same rule to be applied in case of my post. If you do not have answer/do not want to help, ZIP/RAR your lips.
Here's the help you need the most...
Do your own effing homework!
Show some effort, get the code as far along as you can on your own. If/when you get stuck, follow the board rules and post the minimum code sample that demonstrated the problem and ask specific questions. Then some of us *might* step in to offer a bit of help.
My definition of homework is exactly what you posted.
Essentially, a ctrl-c/ctrl-v from your tutors assignment.
Now, if you had followed up with "well my approach so far is ... which works .... but doesn't work ...." would as least have shown that you had made an effort.
But as it is, your stock is zero, because all you want to do is tell other people how to answer questions.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I see! So you need proof for approach! Okay! Here it is..
I tried to solve it using XOR approach, from where I could not conclude anything fruitful.
Also, I cannot apply sorting as O(nlogn) would be necessary. Using HashMap needs so much of space.
Any other help please?
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.
Last edited by whiteflags; 03-24-2011 at 01:29 AM.
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".
Last edited by lattica; 03-25-2011 at 01:52 AM. Reason: brainfart
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.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
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.
Last edited by maxorator; 03-25-2011 at 03:12 AM.
"The Internet treats censorship as damage and routes around it." - John Gilmore
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.
On unsorted data, binary search doesn't even work, so I don't understand what you're saying.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.
Last edited by whiteflags; 03-25-2011 at 08:20 AM.
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.
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.
Last edited by maxorator; 03-26-2011 at 07:58 PM.
"The Internet treats censorship as damage and routes around it." - John Gilmore
What I find very disappointing is that you don't seem to be able to reach even this most basic requirement. Do you have a grasp of Big O notation (honest question)?
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
1. You posted this exact same question almost exactly a year ago, on this board. What the heck? Does your brain go through an annual cycle or something?
2. Here's the beginning of an idea, though I haven't worked it out to the end, and it might not be fruitful, but here goes.
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. SO. One by one, go through the elements and subtract them from the sum. If the element you subtract happens to be xk, the result will be divisible by three!
However, there is a glitch. Suppose you subtract x1, which isn't the element you are looking for. You end up with:
3*(x1+x2+...)+xk-x1 = 2*x1+3*(x2+x3+...)+xk
This WILL be divisible by three, if 2*x1+xk happens to be divisible by three, which could happen.
That's as far as I've gotten. This idea could become a workable strategy, or maybe not. Also, there is a problem if there are zeros in the array. Zero can be divided by three an infinite number of times, so that needs to be a special case.
Can anyone flesh out this line of reasoning? Or is it a dead end?
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
Why is that so? It would be helpful if you throw some light on this.
Thanks for helping! but read my previous question out carefully. The 2 questions are different.
Last edited by anirban; 03-22-2011 at 09:56 PM.
