what is gray code?
- binary numeral system where two successive values differ in only one bit
- this means if you list all the gray codes in an order, you get a sequence such that each value differs from the next by exactly one bit
a common formula to get the i-th gray code for n bits is :
g(i)=i⊕(i≫1)
where ⊕ is the bitwise XOR operator, and ≫ is the right-shift operator.
💡 Explanation of Solution
1. generate all gray codes for n bits
- we know 2^n is the total number of codes we need
- for each integer i from 0 to size-1, compute its gray code using i⊕(i≫1)
- store these gray codes in a vector `gray`
2. identify the starting index of the given start value
- look through the generated gray codes to find which index corresponds to the integer start
3.rotate the gray code sequence so it starts at `start`
- once we know where start is, we take all gray codes from startIndex onward, wrap around circularly, and store them in result
- the modulo % size ensures circular wrapping, if we go beyond the end of the array
⌛ Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(2^n)
both bound by the number of gray codes / permutations of n
💻 Implementation of Solution
class Solution {public: vector<int> circularPermutation(int n, int start) { int size = 1 << n; // 2^n vector<int> gray(size); // 1) Generate Gray code: g(i) = i ^ (i >> 1) for (int i = 0; i < size; ++i) { gray[i] = i ^ (i >> 1); } // 2) Find the index of 'start' in the Gray code int startIndex = 0; for (int i = 0; i < size; ++i) { if (gray[i] == start) { startIndex = i; break; } } // 3) Rotate the Gray code to begin at 'start' vector<int> result(size); for (int i = 0; i < size; ++i) { result[i] = gray[(startIndex + i) % size]; } return result; }};