single number I II

single number I II

Single number I

a^a == 0, if I know this, this problem would not be hard.

 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int sum = 0;
 5         for ( int i = 0; i < n; i++ ) {
 6             sum ^= A[i];
 7         }
 8         return sum;
 9     }
10 };

Single number II

This is a little harder. Use bit operation to solve this question. Assuming one, two, three stand for numbers apperars one, two and three times. Check two first, then check one and three.

 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int one = 0;
 5         int two = 0;
 6         int three = 0;
 7         for ( int i = 0; i < n; i++ ) {
 8             two |= one&A[i];
 9             one = one^A[i];
10             three = one&two;
11             two &= ~three;
12             one &= ~three;
13         }
14         return one;
15     }
16 };

Loading Disqus comments...
Table of Contents