Single number: coding problems under constant space

Image for post
Image for post
Photo by Michael Dziedzic on Unsplash

Values of good problems
Good problems are problems with layers and depth. Solving good problems is an exploration of problem-solving territory and gives a new perspective. A classic example is Fermat’s last theorem. It is a problem that takes 350 years to solve. To solve Fermat’s last theorem, several fields of mathematics have been invented.

Warm-up problem: You are given a cup of peanuts. Your job is to find out whether the number of peanuts is odd or even. However, you can only count from 0 to 1.

Obviously, standard counting does not work because you only count to 1. However, the answer to this problem is either odd or even. Odd and even are just two states that could be encoded with 0 and 1. You can count peanuts by counting 0 and 1 alternately. The number of peanuts is odd if your last count is 0. Otherwise, the number of peanuts is even. We are now ready for single-number problems.

Next, we will discuss Single number 1, 2 and 3 problems from Leetcode.com. Let’s start.

Single number 1

Single number 1: Given an array of integers called nums, every element appears twice except for one. Find that single one. You are only allowed to use constant space.
Example: nums = [5,5,4]. Output: 4

Similar to the warm-up problem, a natural place to start is encoding. We can encode each number as binary bits. In the Table 1, nums = [5, 5, 4].
Each number in nums is encoded using 3 binary bits. Encoding all numbers in binary form, we can find the single number by counting each bit of all numbers. For each bit, either # of 0s or # of 1s is odd. In Table 1, there are 3 of 1s in bit-1. Note that all numbers except the single number appear twice. The fact that # of 1s in bit-1 is odd implies that the bit-1 of the single number is 1.

Image for post
Image for post

Similarly, we can find bit-i of the single number as follows:

i) Count #of 0s and # of 1s of the bit-i of
all numbers.
ii) Let n0 = # of 0s; n1 = # of 1s
iii) If n0 is odd, the bit-i of the single number is 0. Otherwise, the bit-i of the single number is 1.

In Table 1, following this process, we find that the single number is 100 or 4. Using this method, the space required for finding the single number is constant and equal to 3 bits in this example.

Single number 2

Single number 2: Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. You are only allowed to use constant space.
Input: [2,2,3,2] Output: 3

In Single number 1, all but the single number appear twice. In Single number 2, all but the single number appear three times. To solve this problem, we need to modify step iii) as follows:

iii) if n0 is 3k+1, the bit-i of the single number is 0. Otherwise, the bit-i of the single number is 1

Now, you might be wondering why Leetcode put Single number 2 as a separate problem with higher difficulty. Single number 2 can be much more difficult than Single number 1 if you solve Single number 1 using XOR bitwise operation. However, using the counting approach discussed above Single number 1 and 2 are pretty much the same problem.

Single number 3

Single number 3: Given an integer array 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. You are only allow to use constant space.
Input: [5,5,3,3,4,2] Output: 4,2

Finding an anchor bit (bit-x) and grouping
Let’s call the two elements that appear only once: Ans0 and Ans1. Because Ans0 and Ans1 are different, there is at least one bit of Ans0 and Ans1 that are different. Let’s call this bit bit-x. How to find such bit-x? We can find bit-x by counting 0s and 1s of each bit. Any bit in which # of 1s and # of 0s are both odd can be bit-x.

Assume nums = [5,5,3,3,4,2]. In the left table below, there are 3 of 0s and 3 of 1s in bit-1. Therefore, we use bit-1 as bit-x. (We can also use bit-2 as bit-x.) On the right table below, we group each number/row according to bit-1. A row is green if its bit-1 is 1. Otherwise, the row is blue.

Image for post
Image for post

Finding the other bits
Without loss of generality, let bit-1 of Ans0 and Ans1 be 0 and 1. To find the other bits of Ans0 and Ans1, we split rows with green and blue highlight into two tables below. Ans0 and Ans1 are now separated. Ans0 (Ans1) is the single number in the left (right) table. To find Ans0 and Ans1, we can easily apply the method for finding the single number in each table. We are done. : )

Image for post
Image for post

Concluding lessons
Thinking and writing about these problems, I have learned the following lessons

  1. Be parsimonious, use only what you need. To know whether a number is odd or even. Only 1 bit is needed.
  2. Stand on related problems. Each problem here is solved incrementally based on the previous problems. To solve problems in such a way, a big picture of how each problem is connected is required.
  3. Start small. Solving Single number 3, I started from finding a bit of Ans1 and Ans2. After finding the anchor bit, other things automatically fall into place.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store