Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

You may also like...