Elements repeated thrice except one

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

[Salem]

I found it in O(1) time.

Do you have any ideas, apart from just dumping your assignment on us?

[anirban]

I found it in O(1) time.

Do you have any ideas, apart from just dumping your assignment on us?

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. Isn't it a great "idea"?

[CommonTater]

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. Isn't it a great "idea"?

By what possible stretch of rules do you think it is appropriate to come in here making demands?

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.

[Salem]

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.

[anirban]

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?

[Mario F.]

Find the element in O(N) time.

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)?

[brewbuck]

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?

[Mario F.]

Elegant The 0 could just be counted. The problem however is that the repeating division will increase O beyond n, no?

If you can find a way to reduce the number in one pass...

[brewbuck]

Elegant The 0 could just be counted. The problem however is that the repeating division will increase O beyond n, no?

If you can find a way to reduce the number in one pass...

I wouldn't consider the divisions to influence the order, because the number of divisions depends on the magnitude of the elements, not the number of elements. Assuming 32-bit integers, you'd never need to divide more than 20 times per element, because 3^21 overflows the range of a 32-bit unsigned int.

But I don't know how to work around the big problem which is 2*x1+xk divisible by three.. I get a feeling like there's a workable method here but I haven't found it yet.

[Mario F.]

I wouldn't consider the divisions to influence the order, because the number of divisions depends on the magnitude of the elements, not the number of elements.

I explained myself badly. I mean that you will be traversing the array twice. Once to perform the division (the sum can be performed here as a running total after division, so we can ignore that), and then finally to check each element against the sum. From my understanding this will give you O(2n). Am I missing something?

I suspect you are close to a solution though. I think however there is a need to reduce the cost if I am indeed right.

But I don't know how to work around the big problem which is 2*x1+xk divisible by three.. I get a feeling like there's a workable method here but I haven't found it yet.

Wouldn't it be the case that the only way it could be divisible by three was if x1 = xk? Because -- I only did some pencil math -- I don't see how it could otherwise.

[brewbuck]

I explained myself badly. I mean that you will be traversing the array twice. Once to perform the division (the sum can be performed here as a running total after division, so we can ignore that), and then finally to check each element against the sum. From my understanding this will give you O(2n). Am I missing something?

Yes, the fact that O(2n) == O(n)

Wouldn't it be the case that the only way it could be divisible by three was if x1 = xk? Because -- I only did some pencil math -- I don't see how it could otherwise.

I was pretty distracted while working it out, so you could be right. I'll play with it some more...

[Mario F.]

Yes, the fact that O(2n) == O(n)

ugh!

I was pretty distracted while working it out, so you could be right. I'll play with it some more...

Well, I'm not actually. Just found the two cases where it isn't. Maybe it will help.

It won't be when xk = 1 and x1 = (a number divisible by 3) + 1
It won't be when x1 and xk = (a number divisible by 3) + 1.

2x4+1 = 9
2x13+1 = 27

2x4 + 13 = 21
2x7 + 10 = 24

We can easily avoid the first by counting ones too, as we are doing for zeroes. The second one... hmm...

[anirban]

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)?

Why is that so? It would be helpful if you throw some light on this.

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?

Thanks for helping! but read my previous question out carefully. The 2 questions are different.

[Mario F.]

Why is that so? It would be helpful if you throw some light on this.

Because the requirement alone usually should hint you about the nature of the solution. A O(N) requirement means a linear approach. As such, any solution that is linear will do. You are not being asked to optimize speed or space. Simply to adhere to a running time. So anything goes, including a hash table that, for a reason which has nothing to do with your requirements, you rejected. Or you can get creative in other ways.

I'll admit the irony however, of having asked you about your understanding of big O, only to make a mistake myself a few posts down. My excuse is that I drew some sort of blank. A dumb moment.