Given an array of n integers, all numbers are unique exception one of them.

• The repeating number repeats n/2 times if n is even

• The repeating number repeats (n-1)/2 or (n 1)/2 times if n is odd

• The repeating number is not adjacent to itself in the array

Write a program to find the repeating number without using extra space.

This is how I tried to solve the problem.

If n is even, then there are n/2 repeating elements. Also, the repeating elements should not be adjacent. So if say there are 6 elements, 3 elements are repeated. The elements can be either at indices 0,2 and 4 or 1,3 and 5. So if I just check if any element repeats at index 0 and 2, and then at index 1 and 3, I can get the repeating element.

If n is odd, then there are 2 choices.

If (n 1)/2 elements are repeating, then we can just check indices 0 and 2. For example say there are 7 elements, 4 of them are repeated, then repeating elements have to be at indices 0,2,4 and 6.

However I cannot find a way to find the (n-1)/2 repeating elements when n is odd. I have thought of using xor and sums but can't find a way.

CodePudding user response：

Let us call the element that repeats as the "majority".

Boyer–Moore majority vote algorithm can help here. The algorithm finds an element that occurs repeatedly for more than half of the elements of the input if any such element exists.

But in your case the situation is interesting. The majority may not occur more than half the times. All elements are unique except the repeating one and repeating numbers are not adjacent. Also, majority element exists for sure.

So,

1. Run majority vote algorithm on numbers at even index in the array. Makes a second pass through the input array to verify that the element reported by the algorithm really is a majority.
2. If in the above step we don't get the majority element, you can repeat the above procedure for numbers at odd index in the array. You can do this second step a bit more smartly because we know for sure that majority element exists. So, any number that repeats would be the result.

In the implementation of above, there is a good scope for small optimizations.

I think I should not explain the majority vote algorithm here. If you want me to, let me know. Apparently, without knowing this majority algorithm we should be able to do it with some counting logic (which would most probably end up the same as the majority algorithm). But just that it's a standard algorithm, we can leverage it.