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 integers in which all the elements are appear thrice but one which appears only one. Write an algorithm to find that element.

Example

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 compare each element with all other elements and return the element which appears only once.

Time Complexity: O(n^2)

Use Hash Map:

  • Store each element as key and its count as value in hash map.
  • Iterate through map and return the element appears once.

Time complexity: O(n), Space complexity: O(n)

Better Approach – O(n) time and O(1) space:

  1. Doing XOR will not help here since all the elements are appear odd number of times.
  2. Sum all the bits in same positions for all the elements and take modulus with 3.
  3. If remainder is 0 i.e if sum is multiple of 3 means that bit is set by elements appearing thrice.
  4. If remainder is not 0 i.e sum is not multiple of 3, it means that bit is set in element appears once for sure. (not sure if that bit is set or unset in elements appearing thrice.)
  5. So if we repeat step 2,3,4 for all the elements for all the positions then we will get the element appearing once. See the example 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:



Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: