Recently, I have been solving LeetCode problems. In addition to participating in the ByteDance 7-day coding challenge, I have been training according to the algorithm template for different types of problems.
I didn't encounter any problems with the sections on binary trees, linked lists, stacks, and queues. Now I have reached the section on binary numbers. Because I had little knowledge about this topic before, I have reached the point where I have to look at the solution for each problem (sad). So I plan to write a blog post to record the thought process for each problem, so that I can review it later.
136. Single Number#
Given a non-empty integer array, every element appears twice except for one. Find that single one.
By using the properties of bitwise operations, where 0^a=a and a^a=0, we can use an initial value of 0 to iterate through the array and perform XOR operations. The remaining value will be the 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 one.
Compared to the previous problem, this one is significantly more difficult, even though only a small change has been made.
Let's review the approach used in the previous problem: we chose to iterate through the array and perform XOR operations because XOR guarantees that calculating the same element twice will return the initial state, i.e., 0=0^a^a. In this problem, the duplicate elements appear three times. Following the approach used in the previous problem, we want to find an operation @ for any number a that satisfies: 0 = 0@a@a@a.
To further explain the situation in the previous problem, let's assume that the number is recorded as 1 and not recorded as 0. By performing XOR operations, we satisfy the following:
Therefore, the numbers that appear twice are all canceled out, and the remaining value represents the record state of the number that appears 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.
We use two variables to represent these two bits (x and y). We want x to be 0^a only when encountering a for the second time, and y to be 0^a only when encountering a for the first time. 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 a and b. Using the approach from the first problem, we can easily find 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 using the bit that is 1 in a^b, we can separate a and b into two different groups. Since the other numbers appear exactly twice, they will be assigned to the same group. This means that both groups are equivalent to the first problem, and we can solve them separately.
Note: To understand the following code, you need to know:
- n&(n-1) can remove the last 1 in the binary representation of n.
- (n&(n-1))^n can obtain the last 1 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 1 from diff (here 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 too simple. We can continuously perform bitwise AND operations and right shifts on the parameter to count the number of 1s.
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 i and use the algorithm from the previous problem for each i. However, this approach has a high complexity. To simplify the solution, we can use dynamic programming and find the recurrence relation.
Let f(i) represent the number of 1s in the binary representation of number i.
The first recurrence relation is obvious: the number of 1s in the binary representation of i is equal to the number of 1s 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 is 11
1 in binary is 1
f(3) = f(1) + 1
---------------------------
4 in binary is 100
2 in binary is 10
f(4) = f(2) + 0
The second recurrence relation is also simple: the number of 1s in the binary representation of i is equal to the number of 1s in the binary representation of i with the last 1 removed, plus 1. For example:
3 in binary is 11
2 in binary is 10
f(3) = f(2) + 1
---------------------------
4 in binary is 100
0 in binary is 000
f(4) = f(0) + 1
The method of removing the last 1 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)
// Or result[i] = result[i & (i-1)] + 1
}
return result
}