Recently, I have been solving LeetCode problems. In addition to participating in ByteDance's seven-day problem-solving challenge, I have been following the Algorithm Template to train by problem type.
The sections on binary trees, linked lists, stacks, and queues were relatively easy and I didn't encounter many problems. Now I have reached the section on binary numbers. Because I had limited knowledge about this topic before, I have reached the point where I have to look at the solution for every problem (sad). So I plan to write a blog post to record the thought process for each problem, for my future reference.
136. Single Number
Given a non-empty integer array, every element appears twice except for one. Find that single element.
By utilizing the properties of bitwise XOR operation (0^a=a and a^a=0), we can use an initial value of 0 to iterate through the array and perform XOR operation. The remaining value will be the single element that appears only once.
package main
func singleNumber(nums []int) int {
result := 0
for _, value := range nums {
result ^= value
}
return result
}
137. Single Number II
Given a non-empty integer array, every element appears three times except for one. Find that single element.
Compared to the previous problem, this one has a significantly higher difficulty level, even though only a small change is made.
Let's review the approach used in the previous problem: we chose to iterate through the array and perform XOR operation because XOR operation ensures that calculating the XOR of the same element twice will return the initial state (0=0^a^a). In this problem, where duplicate elements appear three times, we want to find an operation @ that, for any number a, satisfies the equation: 0 = 0@a@a@a.
To further explain the situation in the previous problem, let's assume that the numbers are recorded as 1 and not recorded as 0. By performing XOR operation, we satisfy the following equation:
Therefore, the numbers that appear twice are completely canceled out, and the remaining value represents the state of the number that appears only once, which is the result.
For binary numbers, each bit can only represent two states, which is not suitable for our situation. Therefore, we can consider using two bits to represent a specific bit in the result. Starting from 00, when encountering the number "a" for the third time, we return to the state 00.
By using two variables to represent these two bits (denoted as x and y), we want to ensure that when encountering "a" for the second time, x is equal to 0^a, and when encountering "a" for the first time, y is equal to 0^a. This way, we can cancel out the numbers that appear three times, and the final state will be 01, with y representing the result.
package main
func singleNumber(nums []int) int {
var x, y int
for _, value := range nums {
y = (y ^ value) & ^x
x = (x ^ value) & ^y
}
return y
}
260. Single Number III
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear twice. Find the two elements that appear only once.
Let's assume that the two elements that appear only once are denoted as "a" and "b". Using the approach from the first problem, we can easily calculate the result of a^b. But how do we find "a" and "b" separately?
Consider the binary representation of a^b. If a bit in the result is 1, it means that the corresponding bits of "a" and "b" are different. By utilizing the bits that are 1 in a^b, we can separate "a" and "b" into two different groups. Since all the other numbers appear twice, they will be assigned to the same group. This means that both groups can be solved using the approach from the first problem.
Note: To understand the following code, you need to know:
- n&(n-1) can remove the last 1 bit in the binary representation of n.
- (n&(n-1))^n can obtain the last 1 bit in the binary representation of n.
package main
func singleNumber(nums []int) []int {
var diff int
for _, value := range nums {
diff ^= value
}
// Let's assume the result is "a" and "b", and the current diff is the result of a^b
// Get any bit that is 1 in diff (in this case, we use the last bit)
diff = (diff & (diff - 1)) ^ diff
result := []int{0, 0}
for _, value := range nums {
if value&diff == 0 {
result[0] ^= value
} else {
result[1] ^= value
}
}
return result
}
191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
This problem is relatively simple. We continuously perform bitwise AND and right shift operations on the parameter to count the number of 1 bits.
func hammingWeight(num uint32) int {
var count int
for num != 0 {
count += int(num & 1)
num >>= 1
}
return count
}
338. Counting Bits
Given a non-negative integer num, for every number i in the range 0 ≤ i ≤ num, calculate the number of 1's in their binary representation and return them as an array.
The simple approach for this problem is to iterate through each number i and use the algorithm from the previous problem to count the number of 1's. However, this approach has a high time complexity. To simplify the solution, we can use dynamic programming and find the recurrence relation.
Let f(i) represent the number of 1's in the binary representation of number i.
The first recurrence relation is straightforward: the number of 1's in the binary representation of i is equal to the number of 1's in the binary representation of i right-shifted by one bit, plus the value of the last bit in the binary representation of i. For example:
3 in binary: 11
1 in binary: 1
f(3) = f(1) + 1
---------------------------
4 in binary: 100
2 in binary: 10
f(4) = f(2) + 0
The second recurrence relation is equally simple: the number of 1's in the binary representation of i is equal to the number of 1's in the binary representation of i with the last 1 bit removed, plus 1. For example:
3 in binary: 11
2 in binary: 10
f(3) = f(2) + 1
---------------------------
4 in binary: 100
0 in binary: 000
f(4) = f(0) + 1
The method of removing the last 1 bit from the binary representation has been mentioned in the Single Number III problem.
package main
func countBits(num int) []int {
result := make([]int, num+1)
for i := 1; i <= num; i++ {
result[i] = result[i>>1] + (i & 1)
// Alternatively, result[i] = result[i & (i-1)] + 1
}
return result
}