Find a special number in an array

Question

There are many numbers in an array and each number appears three times excepting for one special number appearing once. Here is the question: how can I find the special number in the array?
Now I can only put forward some methods with radix sorting and rapid sorting which cannot takes advantage the property of the question. So I need some other algorithms.
Thanks for your help.

Answer 1

Add the numbers bitwise mod 3, e.g.

def special(lst):
    ones = 0
    twos = 0
    for x in lst:
        twos |= ones & x
        ones ^= x
        not_threes = ~(ones & twos)
        ones &= not_threes
        twos &= not_threes
    return ones

Answer 2

Since nobody's saying it, I will: hashtable.

You can calculate how many times each element occurs in the array in O(n) with simple hashtable (or hashmap).

Answer 3

Following is another O(n) time complexity and O(1) extra space method

suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3.

The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider

the example array {5, 5, 5, 8}.

The 101, 101, 101, 1000

Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0;

Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0;

Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0;

Sum of fourth bits%3 = (1)%3 = 1;

Hence number which appears once is 1000

#include <stdio.h>
#define INT_SIZE 32

int getSingle(int arr[], int n)
{
// Initialize result
int result = 0;

int x, sum;

// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++)
{
  // Find sum of set bits at ith position in all
  // array elements
  sum = 0;
  x = (1 << i);
  for (int j=0; j< n; j++ )
  {
      if (arr[j] & x)
        sum++;
  }

  // The bits with sum not multiple of 3, are the
  // bits of element with single occurrence.
  if (sum % 3)
    result |= x;
}

return result;
}

// Driver program to test above function
int main()
{
int arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",getSingle(arr, n));
return 0;
}

Answer 4

If the array is sorted, the problem is trivial, you just loop through the list, three items at a time, and check if the third item is the same as the current.

If the array is not sorted, you can use a Hash Table to count the number of occurences of each numbers.

Answer 5

A possible algorithm (very generic, not tested) :

function findMagicNumber(arr[0...n])
   magic_n := NaN

   if n = 1 then
      magic_n := arr[0]
   else if n > 1 then
      quicksort(arr)

      old_n := arr[0]
      repeat := 0

      for i := 1 to n
         cur_n := arr[i]
         repeat := repeat + 1
         if cur_n ≠ old_n then
            if repeat = 1 then
               magic_n := old_n
            old_n := cur_n
            repeat := 0

   return magic_n

Answer 6

I didnt find the implementation of bitwise mod 3 very intuitive so I wrote a more intiuitive version of the code and tested it with various examples and it worked. Here is the code inside the loop

threes=twos&x //=find all bits counting exactly thrice
x&=~threes    //remove the bits countring thrice from x as well as twos
twos&=~threes

twos|=ones&x //find all bits counting exactly twice
x&=~twos  //remove all bits counting twice from modified x as well as ones
ones&=~twos

ones|=x //find all the bits from previous ones and modified x

Hope you guys find it easy to understand this version of code.

Answer 7

How about the following?

If we assume that you know the maximum and minimum values of all numbers in the array (or can at least limit them to some maximum range, say max - min + 1, then create an auxiliary array of that size, initialized to all zeros, say AuxArray[].

Now scan your original array, say MyArray[], and for each element MyArray[i], increment AuxArray[MyArray[i]] by one. After your scan is complete, there will be exactly one element in AuxArray[] that equals one, and the index of that element in AuxArray[] will be the value of the special number.

No complicated search here. Just a linear order of complexity.

Hope I've made sense.

John Doner

Answer 8

I got a solution. It's O (n) time and O (1) space.

n=list(map(int,input().split()))
l=[0]*64
for x in n:
    b=bin(x)[2:]
    b='0'*(64-len(b))+b
    i=0
    while i<len(l):
        l[i]+=int(b[i])
        i+=1
i=0
while i<len(l):
    l[i]%=3
    i+=1
s=''
for x in l:
    s+=str(x)
print(int(s,2))

Answer 9

    int main()
    {
           int B[] = {1,1,1,3,3,3,20,4,4,4};
           int    ones = 0 ;
           int    twos = 0 ;
           int not_threes;
           int x ;

       for( i=0; i< 10; i++ )
       {
        x =  B[i];
            twos |= ones & x ;
            ones ^= x ;
            not_threes = ~(ones & twos) ;
            ones &= not_threes ;
            twos &= not_threes ;
        }

        printf("\n unique element = %d \n", ones );

        return 0;

    }


The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.