Reference: Problem I, Problem II, Problem III EPI 11.10

Difficulty: Medium

My Post: All-In-One Summary (Single Number I, II, III)

## Single Number I

Given a

`non-empty`

array of integers, every element appears twice except for one. Find that single one.

**Follow-up:** Your algorithm should have a `linear runtime`

complexity. Could you implement it `without using extra memory`

?

**Example:**

1 | Input: [2,2,1] |

**Methods:**

- Brute-force

`Option 1`

: Check each item with the rest of items.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17public int singleNumber(int[] nums) {

int n = nums.length;

for (int i = 0; i < n; ++i) { // examining i

boolean isSingle = true;

for (int j = 0; j < n; ++j) {

if (i == j) continue; // except itself

if (nums[i] == nums[j]) { // found duplicate numbers

isSingle = false;

}

}

if (isSingle) {

return nums[i];

}

}

throw new IllegalArgumentException();

}**Time:**$O(N^2)$**Space:**$O(1)$`Option 2`

:- Iterate over all the elements in
`nums`

. - If some number in
`nums`

is new to array, append it. - If some number is already in the array, remove it.
**Time:**$O(N^2)$**Space:**$O(N)$

- Iterate over all the elements in

- Hash Table
- For the
`Option 2`

above, we can optimize it by using a hash set since`add`

and`remove`

operations take only $O(1)$ time. - The way to get the value in a set is to iterate it.
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15// HashSet

public int singleNumber(int[] nums) {

Set<Integer> set = new HashSet<>();

for (int val : nums) {

if (set.contains(val)) {

set.remove(val);

} else {

set.add(val);

}

}

for (int val : set) {

return val;

}

throw new IllegalArgumentException();

}**Time:**$O(N)$**Space:**$O(N)$

- For the
- Math
- Use the following equation to solve the problem:
- $2 \times (a + b + c) - (a + a + b + b + c) = c$
1

2

3

4

5

6

7

8

9

10

11

12

13public int singleNumber(int[] nums) {

int sum = 0;

Set<Integer> set = new HashSet<>();

for (int val : nums) {

sum += val;

set.add(val);

}

int setSum = 0;

for (int val : set) {

setSum += val;

}

return 2 * setSum - sum;

}**Time:**$O(N)$**Space:**$O(N)$

- Bit Manipulation
- If we take
`XOR`

of zero and some bit, it will return that bit:`a ^ 0 = a`

- If we take
`XOR`

of two same bits, it will return $0$:`a ^ a = 0`

- So we have:
`a ^ b ^ a = (a ^ a) ^ b = b`

. - The numbers that occur twice will be reduced to zero.
1

2

3

4

5

6

7public int singleNumber(int[] nums) {

int a = 0;

for (int val : nums) {

a ^= val;

}

return a;

}**Time:**$O(N)$**Space:**$O(1)$

- If we take

## Single Number II

Given a

`non-empty`

array of integers, every element appears three times except for one. Find that single one.

**Follow-up:** Your algorithm should have a `linear runtime`

complexity. Could you implement it `without using extra memory`

?

**Example:**

1 | Input: [2,2,3,2] |

**Methods**

- Brute-force (same as Problem I)
- Hash Table
- Use a hash map to count the number of occurrence.
**Time:**$O(N)$**Space:**$O(N)$

- Math (same as Problem I)
- $3 \times (a + b + c) - (a + a + a + b + b + b + c) = c$

- Bit Manipulation (Generalized)
- See details below.

1 | // k = 3 / 11 (m = 2), p = 1 |

## Generalized Method

Reference: Detailed explanation and generalization of the bitwise operation method for single numbers

### Design Counting System

#### Update A State

The problem can be generalized as follows:

- Given an array of integers, every element appears
`k`

(`k > 1`

) times except for one which appears`p`

times (`p >= 1, p % k != 0`

). Find that single one.

The idea is to design a way to count the number of 1-bit digits. If the number of 1-bit digits equals `k`

, we restore the counting system to `0`

and make it start over.

To represent this counting system, we can use `m-bit`

binary form `xm, ..., x2, x1`

. Here are four properties of the counter:

- There is an initial state of the counter, say $0$.
- For each input, if we hit
`0`

, the counting bit`xi`

should remain unchanged. - Otherwise (hit
`1`

), the bit should increase by one. - In order to cover
`k`

counts (states), we require`2^m >= k`

, which means we need`m`

bits that satisfy`m >= logk`

.

For example, if we need three states (`k = 3`

), we can use `m = 2`

bits to represent this.

- State 1:
`x2 = 0, x1 = 0`

- State 2:
`x2 = 0, x1 = 1`

- State 3:
`x2 = 1, x1 = 0`

The key part is: how each bit changes as we are going through the array.

1 | x3 x2 x1 |

We can observe that:

- The
`x1`

column changes from 0 to 1 or from 0 to 1 successively, and if it encounter a`1`

, it should change. So we can use bit-toggle operation`^= 1`

.`x1 = x1 ^ val`

(val could be`1`

or`0`

)

- The
`x2`

column changes when`x1`

changes from`0`

to`1`

. Thus we can express this as follows:`x2 = x2 ^ (x1 & val)`

- The
`x3`

column then could be expressed similarly:`x3 = x3 ^ (x2 & x1 & val)`

- To generalize,
`xm`

could be expressed as follows:`xm = xm ^ (xm-1 & ... & x2 & x1 & val)`

#### Reset A State

Also, we need to design a cutting mechanism to reset the counting if it hits one for `k`

times. To this end, we apply bitwise `AND`

to those `x`

values with some `mask`

to reset the bits.

Specifically, we want a `mask`

that will be `0`

only when the count reaches `k`

and be `1`

for all other count cases.

How do we achieve that?

For example, check out the examples when `k = 2`

and `k = 3`

:

1 | x2 x1 +1 x2 x1 => x2 x1 |

When the bits of `x`

are the same as `k`

‘s, it should be reset.

- If the bit of
`k`

is`1`

, the`mask`

should be`~x`

. - If the bit of
`k`

is`0`

, the`mask`

should be`x`

.

Combining all of them together:

- The
`mask`

should be`~(ym & ... & y2 & y1)`

.- If
`k = 1`

,`y = x`

. - If
`k = 0`

,`y = ~x`

.

- If

Therefore, as for the examples above:

`k = 2 (1 0)`

: the mask is`~(x2 & ~x1)`

.`k = 3 (1 1)`

: the mask is`~(x2 & x1)`

.

One more example for `k = 5 (101)`

, the mask is `~(x3 & ~x2 & x1)`

.

#### Combination

To this point, we can write out the code for this counting system for `k = 3`

:

1 | int x1 = 0, x2 = 0; |

### Back To Problem

It’s time to generalize our results from 1-bit number case to 32-bit integers. With the help of bitwise operations, we may be able to manage all the 32 bits (counters) collectively instead of using 32 32-bit integers.

The question is how to get the result from the `x`

values in those counters. By now, we notice that the counters’ states are only contributed by the number we want. Let’s say the number appear $p$ times, so there should be $p$ `1`

which have entered the counters. Since $p$ could be very large, we need to do `p' = p % k`

to know the exact numbers of `1`

.

Notice that if `p % k == 0`

, this method is no longer effective for this problem.

For example, if

`k = 2 (1 0), p = 1 (0 1)`

, the final state of`1`

‘s corresponding counter’s state should be`x2 = 0, x1 = 1`

. So we just need to return`x1`

as our result.For another example, if

`k = 2 (1 0), p = 2 (1 0)`

, the final state of`1`

‘s corresponding counter’s state should be`x2 = 0, x1 = 0`

. However, since it is also the same case of`0`

, we cannot extract the bits that are`1`

.For another example , if

`k = 4 (1 0 0), p = 3 (0 1 1)`

, the final state of`1`

‘s corresponding counter’s state should be`x3 = 0, x2 = 1, x1 = 1`

. So, we just need to return`x2 | x1`

, or`x2`

, or`x1`

as our results.

## Single Number III

Given an array of numbers

`nums`

, in which`exactly two elements`

appear only once and all the other elements appear`exactly twice`

. Find the two elements that appear only`once`

.

**Note:** The order of the result is not important. So in the above example, `[5, 3]`

is also correct.

**Follow-up:** Your algorithm should have a `linear runtime`

complexity. Could you implement it `without using extra memory`

?

**Example:**

1 | Input: [1,2,1,3,2,5] |

**Methods**

- Brute-force (same as Problem I)
- Use
`stream()`

to convert`List<Integer>`

to`int[]`

.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19public int[] singleNumber(int[] nums) {

int n = nums.length;

List<Integer> result = new ArrayList<>();

for (int i = 0; i < n; ++i) { // examing i

boolean isSingle = true;

for (int j = 0; j < n; ++j) {

if (i == j) continue; // except itself

if (nums[i] == nums[j]) { // found duplicate numbers

isSingle = false;

}

}

if (isSingle) {

result.add(nums[i]);

}

}

return result.stream().filter(Objects::nonNull).mapToInt(Integer::intValue).toArray();

// OR: return new int[] { result.get(0), result.get(1) };

}

- Use
- Hash Table
- Use a hash set.
1

2

3

4

5

6

7

8

9

10

11public int[] singleNumber(int[] nums) {

Set<Integer> set = new HashSet<>();

for (int val : nums) {

if (set.contains(val)) {

set.remove(val);

} else {

set.add(val);

}

}

return set.stream().filter(Objects::nonNull).mapToInt(Integer::intValue).toArray();

}**Time:**$O(N)$**Space:**$O(N)$

- Use a hash set.
- Math (not applicable)
- Bit Manipulation (reference)
- This time we need one more trick. We need to put those distinct single numbers into two groups.
- Let
`a`

and`b`

be the two unique numbers. **In the first pass**, we use`^`

to get the value`a ^ b`

. With this value, we extract any bit which has value`1`

. The bit values of`a`

and`b`

in this position must be different.**In the second pass**, we separate numbers into two groups, one group with that bit set, and another group with that bit unset.- Notice that the size of each group could be different, but we have guaranteed that
`a`

and`b`

are not in the same group, and other same numbers are in the same group (`since they both have that bit set or unset`

).

- Notice that the size of each group could be different, but we have guaranteed that
- Under this condition, we can extract
`a`

and`b`

in each group by the method proposed in the Problem I.

**Time:**$O(N)$

**Space:**$O(1)$

**Note:** Be careful of the precedence of `&`

and `>`

.

1 | public int[] singleNumber(int[] nums) { |