Dare2Solve
The problem is to generate the sequence of Gray codes for a given number n
. A Gray code sequence is a sequence of 2^n
integers where the binary representation of each integer differs from the previous one by exactly one bit. The sequence starts with 0
and must include all 2^n
numbers exactly once.
The key idea behind generating Gray codes is to ensure that each successive number in the sequence differs from the previous one by only one bit. This can be achieved by flipping one bit at a time, starting from the least significant bit. By tracking which numbers have already been visited, we can ensure that the sequence is valid and contains all the necessary numbers.
0
and mark it as visited.2^n
numbers have been added to the result.The time complexity is O(2^n * n)
. This is because there are 2^n
numbers in the sequence, and for each number, we may need to explore up to n
possible next steps.
The space complexity is O(2^n)
for storing the sequence and the set of visited numbers.
class Solution {
public:
std::vector<int> grayCode(int n) {
std::vector<int> result = {0};
std::unordered_set<int> visited = {0};
std::function<bool(int)> generateGrayCode = [&](int num) {
if (result.size() == pow(2, n)) return true;
for (int i = 0; i < n; i++) {
int next = num ^ (1 << i);
if (visited.find(next) == visited.end()) {
result.push_back(next);
visited.insert(next);
if (generateGrayCode(next)) return true;
result.pop_back();
visited.erase(next);
}
}
return false;
};
generateGrayCode(0);
return result;
}
};
class Solution:
def grayCode(self, n: int) -> list[int]:
result = [0]
visited = set([0])
def generateGrayCode(num):
if len(result) == 2 ** n:
return True
for i in range(n):
next_num = num ^ (1 << i)
if next_num not in visited:
result.append(next_num)
visited.add(next_num)
if generateGrayCode(next_num):
return True
result.pop()
visited.remove(next_num)
return False
generateGrayCode(0)
return result
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> result = new ArrayList<>();
result.add(0);
Set<Integer> visited = new HashSet<>();
visited.add(0);
if (generateGrayCode(0, n, result, visited)) {
return result;
}
return result;
}
private boolean generateGrayCode(int num, int n, List<Integer> result, Set<Integer> visited) {
if (result.size() == (1 << n)) return true;
for (int i = 0; i < n; i++) {
int next = num ^ (1 << i);
if (!visited.contains(next)) {
result.add(next);
visited.add(next);
if (generateGrayCode(next, n, result, visited)) return true;
result.remove(result.size() - 1);
visited.remove(next);
}
}
return false;
}
}
var grayCode = function (n) {
const result = [0];
const generateGrayCode = (num, visited) => {
if (result.length === Math.pow(2, n)) return true;
for (let i = 0; i < n; i++) {
const next = num ^ (1 << i);
if (!visited.has(next)) {
result.push(next);
visited.add(next);
if (generateGrayCode(next, visited)) return true;
result.pop();
visited.delete(next);
}
}
return false;
};
generateGrayCode(0, new Set([0]));
return result;
};