**Problem:**

Please find the problem here.

**Solution:**

We already solved Single Number, so all we have to do is to generalize it. Considering exclusive-or as addition modulo 2, all we really need is addition modulo 3, and do that per digit.

So the first step is to extend the number into a base 3 number instead of base 2. As binary representation, we will need one more bit per bit, so I used an 64-bit integer, the most significant 32 bits are the most significant bit for the digit. So it is represented like this:

Base 3 representation: 2 0 1 0

Binary representation

**0**

__1__**0**

__0__**1**

__0__**0**

__0__Represented in code:

__1__

__0__

__0__**0 0 1 0**

__0__The cool thing about this representation is that we can change a number into its base 3 version simply by adding a bunch of 0 before it, and obviously, we can extract the original number by just taking the lowest 32 bits.

So we simply extract each digit, add it, modulo 3, and put it back, nothing special about that.

Last but not least, if somehow the array has 3n +

**2**elements, we need to

**the number by 2. It can be easily done by multiplying it with the multiplicative inverse of 2, which is 2 again because (2 x 2 = 4 = 1 mod 3).**

__divide__Be careful with signed integer, we need to explicitly cast it to unsigned to avoid sign extension.

**Code:**

#include "stdafx.h"// https://leetcode.com/problems/single-number-ii/#include "LEET_SINGLE_NUMBER_II.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std;namespace _LEET_SINGLE_NUMBER_II{typedef long long int64;class Solution{public:int singleNumber(int A[],int n) {int64 accumulator=0;for(int i=0;i<n;i++) {int64 lo_mask=1;int64 hi_mask= (int64)1<<32;for(int d=0;d<32;d++) {int64 ac_lo=accumulator&lo_mask;int64 ac_hi=accumulator&hi_mask;int64 ar_lo= (unsigned int)A[i] &lo_mask;int64 ar_hi= (unsigned int)A[i] &hi_mask;int ac_digit= ((ac_hi==0) ?0:2) + ((ac_lo==0) ?0:1);int ar_digit= ((ar_hi==0) ?0:2) + ((ar_lo==0) ?0:1);int sum= (ac_digit+ar_digit) %3;accumulator=accumulator& ~lo_mask;accumulator=accumulator& ~hi_mask;switch(sum) {case 0:// The digit is already resetbreak;case 1:accumulator=accumulator|lo_mask;break;case 2:accumulator=accumulator|hi_mask;break; }lo_mask=lo_mask<<1;hi_mask=hi_mask<<1; } }if(n%3==2) {int64 lo_mask=1;int64 hi_mask= (int64)1<<32;for(int d=0;d<32;d++) {int64 ac_lo=accumulator&lo_mask;int64 ac_hi=accumulator&hi_mask;int ac_digit= ((ac_hi==0) ?0:2) + ((ac_lo==0) ?0:1);int quoient= (ac_digit*2) %3;accumulator=accumulator& ~lo_mask;accumulator=accumulator& ~hi_mask;accumulator=accumulator& ~lo_mask;accumulator=accumulator& ~hi_mask;switch(quoient) {case 0:// The digit is already resetbreak;case 1:accumulator=accumulator|lo_mask;break;case 2:accumulator=accumulator|hi_mask;break; }lo_mask=lo_mask<<1;hi_mask=hi_mask<<1; } }return(accumulator<<32) >>32; } }; };using namespace _LEET_SINGLE_NUMBER_II;int LEET_SINGLE_NUMBER_II() {int A[] = { -2, -2,1,1, -3,1, -3, -3, -4, -2};Solution solution;cout<<solution.singleNumber(A,10) <<endl;return 0; }

Here is another solution

ReplyDeletepublic class Solution {

public int singleNumber(int[] nums) {

int p = 0;

int q = 0;

for(int i = 0; i<nums.length; i++){

p = q & (p ^ nums[i]);

q = p | (q ^ nums[i]);

}

return q;

}

}

Analysis from this blog post : http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html