# Easy to understand: dynamic programming

• I should have added some explanations. We use the same idea for Single Number I. We compute each bit modulo 3. For each bit, 1 can appear for 3k+1, 3k+2, or 3k times. Eventually, we use the 3k+1-type bits. So we want to record three sets of data dynamically: the bits on those positions 1 has appeared 3k+1 times; the bits on those positions 1 has appeared 3k+2 times, and the bits on those positions 1 has appeared 3k times. I use three integers to record these 3 sets of bits, where I call them: one, two, three.

Using the idea of Dynamic Programming, we can give the recursion formula. The bits of 1 in the new number will change 3k+1-type bits to 3k+2-type bits, and 3k+2-type bits to 3k-type bits. Similarly, the bits of 0 in the new number will remain 3k+1-type bits to 3k+1-type bits. One can many different ways to write the recursion formula. I just give one as follows.

``````class Solution {
public:
int singleNumber(vector<int>& nums) {
int one=nums[0], two=0, three=~nums[0], temp1, temp2;
for (int i=1; i<nums.size(); i++){
temp1= (one & nums[i])|(two & (~nums[i])) ;//two
temp2= (three &  nums[i])|(one & (~nums[i]));//one
one=temp2;
two=temp1;
three=~(one|two);
}
return one;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.