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 at the beginning. Now I have reached the section on binary numbers. Due to my limited knowledge in this area, 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, 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, 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, which appears exactly once. Find that single one.
Compared to the previous problem, this one is significantly more difficult despite only a slight modification.
Let's review the solution to the previous problem: we chose to iterate through the array and perform XOR operations because XOR guarantees that performing the operation twice on the same element will return the initial state, i.e., 0=0^a^a. In this problem, the duplicate elements appear three times. Following the same approach as the previous problem, we want to find an operation @ for any number a such that: 0 = 0@a@a@a.
To further explain 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 completely canceled out, and the remaining value represents the record 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 case. Therefore, we can consider using two binary digits to represent a specific bit in the result, starting from 00 and returning to 00 after encountering a.
By using two variables to represent these two digits (denoted as x and y), we want x to be 0^a when a is encountered for the second time, and y to be 0^a when a is encountered for the first time. This way, we can cancel out the numbers that appear three times, and the result will be in the state 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 bit in a and b is 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 are equivalent to the previous 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 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 (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 to 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 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 in 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
}