grid47 Exploring patterns and algorithms
Oct 29, 2024
5 min read
Solution to LeetCode 89: Gray Code Problem
Given an integer n, generate an n-bit Gray code sequence. A Gray code sequence is a sequence of integers where each integer’s binary representation differs from the next one by exactly one bit. The first integer in the sequence is always 0, and every integer appears only once in the sequence. The binary representation of the first and last integers should also differ by exactly one bit.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n, representing the number of bits in the Gray code sequence.
Example: Input: n = 3
Constraints:
• 1 <= n <= 16
Output: The output should be a list of integers that represent a valid n-bit Gray code sequence.
Example: Output: [0, 1, 3, 2, 6, 7, 5, 4]
Constraints:
• Each integer in the sequence must be a valid n-bit number.
Goal: The goal is to generate a sequence of integers such that every adjacent pair of integers differs by exactly one bit in their binary representation, and the first and last integers differ by exactly one bit.
Steps:
• Start with the sequence containing only the integer 0.
• Iteratively generate the next integer by flipping a bit in the binary representation of the integers already in the sequence, ensuring that each new integer differs by exactly one bit from the previous one.
Goal: The input value n will always be between 1 and 16, inclusive.
Steps:
• The sequence must contain exactly 2^n integers.
• The binary representation of each integer should be n bits long.
Assumptions:
• The input value n is always within the specified range (1 <= n <= 16).
• The Gray code sequence will be valid for any input within this range.
• Input: Input: n = 2
• Explanation: For n = 2, a valid Gray code sequence is [0, 1, 3, 2]. The binary representations are: 00, 01, 11, 10. Each adjacent pair of numbers differs by exactly one bit.
• Input: Input: n = 3
• Explanation: For n = 3, a valid Gray code sequence is [0, 1, 3, 2, 6, 7, 5, 4]. The binary representations are: 000, 001, 011, 010, 110, 111, 101, 100. Each adjacent pair of numbers differs by exactly one bit.
Approach: To generate the Gray code sequence, we can use an iterative method. Start with a list containing only 0, then iteratively construct the sequence by reflecting the current list and flipping the appropriate bits to generate the new sequence.
Observations:
• The Gray code sequence for any given n can be generated from the sequence of n-1 bits by reflecting it and flipping the appropriate bits.
• By iteratively constructing the sequence for smaller bit sizes, we can use previously computed results to generate the Gray code sequence for larger sizes.
Steps:
• Start with the sequence [0] for 0-bit Gray code.
• For each bit from 1 to n, reflect the current sequence and flip the highest bit of each element in the reflected sequence.
• Append the flipped values to the original sequence to form the new sequence.
Empty Inputs:
• The input will always have a valid value for n (1 <= n <= 16).
Large Inputs:
• For n = 16, the sequence will contain 65536 integers, so ensure that the algorithm can handle large sequences efficiently.
Special Values:
• For n = 1, the sequence will be [0, 1].
Constraints:
• The Gray code sequence must be valid for any n between 1 and 16.
vector<int> grayCode(int n) {
vector<int> res = {0};
for (int i =0; i < n; i++) {
int size = res.size();
for (int j = size -1; j >=0; j--) {
res.push_back(res[j] | (1<< i));
}
}
return res;
}
1 : Function Declaration
vector<int> grayCode(int n) {
Declares a function `grayCode` that takes an integer `n` representing the number of bits and returns a vector of integers representing the Gray code.
2 : Array Initialization
vector<int> res = {0};
Initializes a vector `res` to store the Gray code, starting with the initial value 0.
3 : Loop Iteration
for (int i =0; i < n; i++) {
Iterates `n` times, where `n` is the number of bits.
4 : Size Calculation
int size = res.size();
Stores the current size of the `res` vector.
5 : Reverse Loop Iteration
for (int j = size -1; j >=0; j--) {
Iterates over the current `res` vector in reverse order.
6 : Bitwise Operations, Array Manipulation
res.push_back(res[j] | (1<< i));
Calculates the next Gray code value by taking the current value `res[j]` and OR-ing it with `1 << i`. This effectively adds the `i`-th bit to the current value. The new value is then added to the end of the `res` vector.
7 : Return
return res;
Returns the final `res` vector containing the generated Gray code.
Best Case: O(2^n), where n is the number of bits. We need to generate 2^n numbers.
Average Case: O(2^n)
Worst Case: O(2^n), since the sequence contains 2^n integers.
Description: The time complexity is linear with respect to the size of the sequence.
Best Case: O(2^n)
Worst Case: O(2^n), since we store the entire Gray code sequence.
Description: The space complexity is linear in the number of integers in the Gray code sequence.
