136. Single Number I, II, III

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:

Input: [2,2,1]
Output: 1
Input: [4,1,2,1,2]
Output: 4

Methods:

Brute-force

Option 1: Check each item with the rest of items.

public 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)$

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.

// 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)$

Math

Use the following equation to solve the problem:

$2 \times (a + b + c) - (a + a + b + b + c) = c$

public 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
  7
  public int singleNumber(int[] nums) {
  int a = 0;
  for (int val : nums) {
  a ^= val;
  }
  return a;
  }
  Time: $O(N)$
  Space: $O(1)$

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:

Input: [2,2,3,2]
Output: 3
Input: [0,1,0,1,0,1,99]
Output: 99

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.

// k = 3 / 11 (m = 2), p = 1
public int singleNumber(int[] nums) {
  int x1 = 0, x2 = 0, mask = 0;
  for (int val : nums) {
    x2 = x2 ^ (x1 & val);
    x1 = x1 ^ val;
    mask = ~(x2 & x1);
    x2 = x2 & mask;
    x1 = x1 & mask;
  }
  // p = 1, final state: x2 = 0, x1 = 1
  return x1;
}

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.

         x3   x2   x1
State 1:  0    0    0
State 2:  0    0    1
State 3:  0    1    0
State 4:  0    1    1
State 5:  1    0    0

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:

          x2   x1  +1  x2   x1  =>  x2   x1
State 1:   0    0       0    1  =>   0    1
State 2:   0    1       1    0  =>   0    1
k = 2:                  1    0  =>   0    0

          x2   x1  +1  x2   x1  =>  x2   x1
State 1:   0    0       0    1  =>   0    1
State 2:   0    1       1    0  =>   0    1
State 3:   1    0       1    1  =>   1    0
k = 3:                  1    1  =>   0    0

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.

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:

int x1 = 0, x2 = 0;
for (int val : nums) {
  // update the state
  x2 = x2 ^ (x1 & val);
  x1 = x1 ^ val;
  // mask
  mask = ~(x2 & x1);
  x2 = x2 & mask;
  x1 = x1 & mask;
}

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 2	Input: [1,2,1,3,2,5] Output: [3,5]

Methods

Brute-force (same as Problem I)

Use stream() to convert List<Integer> to int[].

public 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) };
}

Hash Table

Use a hash set.

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);
    }
  }
  return set.stream().filter(Objects::nonNull).mapToInt(Integer::intValue).toArray();
}

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

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).
- 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 >.

public int[] singleNumber(int[] nums) {
  // First Pass
  int abXor = 0;
  for (int val : nums) {
    abXor ^= val;
  }
  
  // Isolate one "1" bit in the abXor
  int mask = abXor & ~(abXor - 1);
  
  // Second Pass
  int a = 0, b = 0;
  for (int val : nums) {
    if ((val & mask) > 0) { // with that bit set
      a = a ^ val;
    } else { // with that bit unset
      b = b ^ val;
    }
  }
  return new int[] { a, b };
}