# All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space

Objec­tive:  Given an array of inte­gers in which all the ele­ments are appear thrice but one which appears only one. Write an algo­rithm to find that element.

Exam­ple

```int [] arrA = {6,5,3,2,4,2,5,6,3,3,6,5,2};
Output: 4
```

Approach:

Naïve Approach: Use nested for loops and com­pare each ele­ment with all other ele­ments and return the ele­ment which appears only once.

Time Com­plex­ity: O(n^2)

Use Hash Map:

• Store each ele­ment as key and its count as value in hash map.
• Iter­ate through map and return the ele­ment appears once.

Time com­plex­ity: O(n), Space com­plex­ity: O(n)

Bet­ter Approach — O(n) time and O(1) space:

1. Doing XOR will not help here since all the ele­ments are appear odd num­ber of times.
2. Sum all the bits in same posi­tions for all the ele­ments and take mod­u­lus with 3.
3. If remain­der is 0 i.e if sum is mul­ti­ple of 3 means that bit is set by ele­ments appear­ing thrice.
4. If remain­der is not 0 i.e sum is not mul­ti­ple of 3, it means that bit is set in ele­ment appears once for sure. (not sure if that bit is set or unset in ele­ments appear­ing thrice.)
5. So if we repeat step 2,3,4 for all the ele­ments for all the posi­tions then we will get the ele­ment appear­ing once. See the exam­ple below
```Say arr[] = {6, 6, 6, 3}

1 1 0
1 1 0
1 1 0
0 1 1
__________+
3 4 1

Now modulus with 3

3mod3  4mod3 1mod3 => 0 1 1 => 3 element appearing once.
```

Code:

Out­put:

`[1, 4, 5, 6, 1, 4, 6, 1, 4, 6]Element appearing once is: 5`