Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
public class Solution { public int singleNumber(int[] A) { // one: The bits that have appeared 1st time or 4th time or 7th time .. etc. // two: The bits that have appeared 2nd time or 5th time or 8th time .. etc. int one = 0, two = 0, three = 0; // Let us take the example of {3, 3, 2, 3} to understand this for (int i = 0; i < A.length; i++) { /* The expression "one & A[i]" gives the bits that are there in both 'one' and new element from A. We add these bits to 'two' using bitwise OR Value of 'two' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ two = two | (one & A[i]); /* XOR the new bits with previous 'one' to get all bits appearing odd number of times Value of 'one' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ one = one ^ A[i]; /* The common bits are those bits which appear third time So these bits should not be there in both 'one' and 'two'. 'three' contains all these bits that appear third time Value of 'three' will be set as 00, 00, 10 and 01 after 1st, 2nd, 3rd and 4th iterations respectively */ three = one & two; /* Remove common bits (the bits that appear third time) from 'one' Value of 'one' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ one = one & (~three); /* Remove common bits (the bits that appear third time) from 'two' Value of 'two' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th itearations respectively */ two = two & (~three); } return one; } }
No comments:
Post a Comment