How do i delete one single unequal element from an array of equal elements without using hashing?

Question

The rules of the question state that:

0. Only one element is different.
1. Rest are all same.
2. Array A size is 8.
3. I need to find the different element and remove it (Hashing cannot be used).

I have not developed the code but I have come up with an algorithm.
There will be two cases one where the different element value is less and other where it has greater value.
Suppose I take case 2, here I compare the sum of 1st 3 elements and the next 3 elements. If both are same, compare A[6] and A[7]. If both are different, suppose 1st 3 elements has greater sum, then compare A[0] and A[1], if they are the same, A[3] is the unequal element, otherwise either A[0] or A[1] is greater, according to their value.

Now my question is what if the array size is $N$>8, what will be the algorithm or code for that?

• greybeard: (There is Do SimpleThings. Does the question require anything beyond remove the single differing element?) What does remove an element from an array mean, exactly?
• Swarnava Chandra Bose: @greybeard here removing means simply deleting the element from array and hence reducing array size by 1. I want an algorithm that can delete one single different element among other similar elements from an Array of size N, without using hashing
• gnasher729: Confused: Why would anyone use hashing? You might as well say "without using a bicycle".
• lox: I don't understand why is hashing relevant (or irrelevant)
• Swarnava Chandra Bose: @lox thats because there is a readymade code available in geeksforgeeks to remove a different element from rest equal elements

Answer 1

• Compare the first two elements (1 comparison.)

• If they are equal, find the different element among the remaining ones ($n-2$ comparisons).

• If they are different, compare the third element to the first (1ドル$ comparison). If they differ, the different element is the first; otherwise the second.

So you conclude in either $n-1$ comparisons (with probability 1ドル-\frac2n$) or in 2ドル$ (with probability $\frac2n$). The expectation is $n-3+\frac6n$, assuming the locations to be equiprobable.

---

Based on Nathaniel's comment, there is a better way:

• find the first pair of distinct elements (at most $m:=\lfloor\frac n2\rfloor$ comparisons);

• conclude with an extra comparison.

More precisely,

• when you found an heterogeneous pair, perform a majority vote with a value from another pair.

• if $n$ is even, you only need to process the first $m-1$ pairs (if they are all homogeneous, the last one is not). Worst case $m = \frac n2$ comparisons; expected case $\frac{1+2+...m-1}m+1 = \frac n4+\frac 12$ comparisons.

• if $n$ is odd, you need to process m pairs; if none is heterogenous, the different element is the last one. Worst case $m+1 = \frac{n+3}2$ comparisons; expected case $\frac{(n-1)(\frac{1+2+...m}m+1)+m}n = \frac n4 +\frac32-\frac 7{4n}$ comparisons.

Note that in the worst case it is impossible to beat $m$ comparisons as you must read all values before you can conclude.

• Nathaniel: I think it is possible to do it in at most $\frac{n}2 + 1$ comparisons if you first find the only pair of distinct elements (generalizing your idea on the first pair).
• user16034: @Nathaniel: you are quite right, though the details need to be worked out. I am updating.

Answer 2

Assuming n >= 3. You have n-1 values x, and one value y.

To determine x, compare any two elements a and b. If they are equal then x=a. Otherwise compare a with a third element c. If a=c then x=a, else x=b.

Now you know x, walk through the array until you find the element ≠ x, and that is what you remove.

• lox: This is a confusing comment, since this answer is generalized to $n \geq 3$.
• Swarnava Chandra Bose: @lox No this is not a confusing comment. Read the question. Of course this answer is generalized to N>=3, but i have said that i need N>8 in the question.
• gnasher729: Guys, what exactly is your problem?

Answer 3

There are many ways to approach this problem, you could:

1. sort the list and then drop the first or last element based on which one isn't equal to a third item in the list (with index 1 ... n-2, where n is the size of the list)
2. you could have two pointers, one at the beginning (p1) and one at the end of the list (p2). p1 moves to the right (towards the end of the list) and p2 moves to the left (towards the beginning of the list) and as they move you capture the cumulative sums (s1 and s2) and stop when s1 != s2, and where the pointers stop then one of these items will be the unequal element. [Note this has an edge case where you have an odd sized list with the unequal element in the middle so code for that]
3. you can check if the first three items and see if any of them are not equal. If so, then you found the unequal element. If not, you have the equal element and so you can keep randomly picking from the list until you find the unequal element.

There are a lot of ways to solve this problem with varying complexities.

• user16034: In your 2., there is no need to accumulate the sums. They will differ just when the two new elements differ. So this reduces to a scheme "process all N/2 pairs", which is optimal.