Program to Find the Number Appearing Once While Others Appearing Thrice

In a given array, each element appears thrice whereas there is an element which appears only once. Write the program to find the element appearing once.
For eg:
      int B[] = {1,1,1,2,2,2,4,3,4,3,4,3,6,7,6,6};

In this above array, element “7” is occurring only once.

Method 1

In order to solve this problem, we can sort the array and then iterate by keeping the count.

Method 2

• Create a hash table.
• Iterate through array and increment counter for each element in hash table.
• Finally iterate through hash table to find which key has counter set to 1.

Method 3

Here we are going to talk about most efficient method to solve the problem.

Algorithm

• Initialize three variable named one,two and three to zero (0)
• Iterate through each element in array and for each element.
  • OR with two and (AND with one and element)
  • XOR the element with variable one.
  • Three = ~(one & two) 

The number saved in “one” will be number occurs only once.

Please note that the same method can be used to find number occurring only twice. In that case, variable “two” will save the number.

Implementation

Let’s have a look into the program to understand it better.

#include <iostream>

/*
 * In a given array each element appears thrice except one which appears only once.
 * Find the element appearing once.
 */

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

   for(int i=0; i< (sizeof(B)/sizeof(B[0])); 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;
}

Let’s look into the output of above program.

 unique element = 7