Given a value N and K, the task is to generate N-bits Gray Code starting from the value K.
Examples:
Input: N = 2, K = 3
Output: 3 2 0 1
Explanation:
3 -> 11
2 -> 10
0 -> 00
1 -> 01
Each value differ by only one bit from the next value in their binary representation.
Input: N = 3, K = 2
Output: 2 3 1 0 4 5 7 6
Approach:
- Gray code are numbers with hamming distance 1 between two consecutive numbers in it.
- The XOR with each element of N bit Gray code generates a sequence of Hamming distance of 1.
- As the first element of N bit Gray code is K, it can be obtained by doing is XOR with 0, i.e. (K ^ 0) = K.
- So the sequence will start with 0 with every consecutive element differ by only one bit in their binary representation.
Below is the implementation of the above approach:
C++
// C++ program Generating N-bit // Gray Code starting from K #include <bits/stdc++.h> using namespace std; // Function to Generating N-bit // Gray Code starting from K void genSequence( int n, int val) { for ( int i = 0; i < (1 << n); i++) { // Generate gray code of corresponding // binary number of integer i. int x = i ^ (i >> 1) ^ val; cout << x << " " ; } } // Driver code int main() { int n = 3, k = 2; genSequence(n, k); return 0; } |
Java
// Java program Generating N-bit // Gray Code starting from K class GFG { // Function to Generating N-bit // Gray Code starting from K static void genSequence( int n, int val) { for ( int i = 0 ; i < ( 1 << n); i++) { // Generate gray code of corresponding // binary number of integer i. int x = i ^ (i >> 1 ) ^ val; System.out.print(x + " " ); } } // Driver code public static void main (String[] args) { int n = 3 , k = 2 ; genSequence(n, k); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program Generating N-bit # Gray Code starting from K # Function to Generating N-bit # Gray Code starting from K def genSequence(n, val) : for i in range ( 1 << n) : # Generate gray code of corresponding # binary number of integer i. x = i ^ (i >> 1 ) ^ val; print (x, end = " " ); # Driver code if __name__ = = "__main__" : n = 3 ; k = 2 ; genSequence(n, k); # This code is contributed by AnkitRai01 |
C#
// C# program Generating N-bit // Gray Code starting from K using System; class GFG { // Function to Generating N-bit // Gray Code starting from K static void genSequence( int n, int val) { for ( int i = 0; i < (1 << n); i++) { // Generate gray code of corresponding // binary number of integer i. int x = i ^ (i >> 1) ^ val; Console.Write(x + " " ); } } // Driver code public static void Main() { int n = 3, k = 2; genSequence(n, k); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript program Generating N-bit // Gray Code starting from K // Function to Generating N-bit // Gray Code starting from K function genSequence(n, val) { for (let i = 0; i < (1 << n); i++) { // Generate gray code of corresponding // binary number of integer i. let x = i ^ (i >> 1) ^ val; document.write(x + " " ); } } // Driver code let n = 3, k = 2; genSequence(n, k); </script> |
2 3 1 0 4 5 7 6
Time Complexity : O(2^n)
Space Complexity : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!