This post is completed by 1 user

  • 1
 Add to List
Hard

240. 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 appear thrice but one which appears only once. 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 a key and its count as the value in the hash map.
  • Iterate through the map and return the element that 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 appear an odd number of times.
  2. Sum all the bits in the same positions for all the elements and take modulus with 3.
  3. If the remainder is 0 i.e if the sum is a multiple of 3 means that the bit is set by elements appearing thrice.
  4. If the remainder is not 0 i.e sum is not multiple of 3, it means that the bit is set in the element and appears once for sure. (not sure if that bit is set or unset in elements appearing thrice.)
  5. So if we repeat steps 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.

Output:

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

Related Problems: