Given a number N, generate bit patterns from 0 to 2^N-1 such that successive patterns differ by one bit.
Examples:
Input: N = 2 Output: 00 01 11 10 Input: N = 3 Output: 000 001 011 010 110 111 101 100
Method-1
The above sequences are Gray Codes of different widths. Following is an interesting pattern in Gray Codes.
n-bit Gray Codes can be generated from list of (n-1)-bit Gray codes using following steps.
- Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
- Modify the list L1 by prefixing a ‘0’ in all codes of L1.
- Modify the list L2 by prefixing a ‘1’ in all codes of L2.
- Concatenate L1 and L2. The concatenated list is required list of n-bit Gray codes
For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list. L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes) L2 = {10, 11, 01, 00} (Reverse of L1) Prefix all entries of L1 with ‘0’, L1 becomes {000, 001, 011, 010} Prefix all entries of L2 with ‘1’, L2 becomes {110, 111, 101, 100} Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100} To generate n-bit Gray codes, we start from list of 1 bit Gray codes. The list of 1 bit Gray code is {0, 1}. We repeat above steps to generate 2 bit Gray codes from 1 bit Gray codes, then 3-bit Gray codes from 2-bit Gray codes till the number of bits becomes equal to n.
Below is the implementation of the above approach:
C++
// C++ program to generate n-bit Gray codes#include <iostream>#include <string>#include <vector>using namespace std;// This function generates all n bit Gray codes and prints the// generated codesvoid generateGrayarr(int n){ // base case if (n <= 0) return; // 'arr' will store all generated codes vector<string> arr; // start with one-bit pattern arr.push_back("0"); arr.push_back("1"); // Every iteration of this loop generates 2*i codes from previously // generated i codes. int i, j; for (i = 2; i < (1<<n); i = i<<1) { // Enter the previously generated codes again in arr[] in reverse // order. Nor arr[] has double number of codes. for (j = i-1 ; j >= 0 ; j--) arr.push_back(arr[j]); // append 0 to the first half for (j = 0 ; j < i ; j++) arr[j] = "0" + arr[j]; // append 1 to the second half for (j = i ; j < 2*i ; j++) arr[j] = "1" + arr[j]; } // print contents of arr[] for (i = 0 ; i < arr.size() ; i++ ) cout << arr[i] << endl;}// Driver program to test above functionint main(){ generateGrayarr(3); return 0;} |
Java
// Java program to generate n-bit Gray codesimport java.util.*;class GfG {// This function generates all n bit Gray codes and prints the// generated codesstatic void generateGrayarr(int n){ // base case if (n <= 0) return; // 'arr' will store all generated codes ArrayList<String> arr = new ArrayList<String> (); // start with one-bit pattern arr.add("0"); arr.add("1"); // Every iteration of this loop generates 2*i codes from previously // generated i codes. int i, j; for (i = 2; i < (1<<n); i = i<<1) { // Enter the previously generated codes again in arr[] in reverse // order. Nor arr[] has double number of codes. for (j = i-1 ; j >= 0 ; j--) arr.add(arr.get(j)); // append 0 to the first half for (j = 0 ; j < i ; j++) arr.set(j, "0" + arr.get(j)); // append 1 to the second half for (j = i ; j < 2*i ; j++) arr.set(j, "1" + arr.get(j)); } // print contents of arr[] for (i = 0 ; i < arr.size() ; i++ ) System.out.println(arr.get(i));}// Driver program to test above functionpublic static void main(String[] args){ generateGrayarr(3);}} |
Python3
# Python3 program to generate n-bit Gray codesimport math as mt# This function generates all n bit Gray# codes and prints the generated codesdef generateGrayarr(n): # base case if (n <= 0): return # 'arr' will store all generated codes arr = list() # start with one-bit pattern arr.append("0") arr.append("1") # Every iteration of this loop generates # 2*i codes from previously generated i codes. i = 2 j = 0 while(True): if i >= 1 << n: break # Enter the previously generated codes # again in arr[] in reverse order. # Nor arr[] has double number of codes. for j in range(i - 1, -1, -1): arr.append(arr[j]) # append 0 to the first half for j in range(i): arr[j] = "0" + arr[j] # append 1 to the second half for j in range(i, 2 * i): arr[j] = "1" + arr[j] i = i << 1 # print contents of arr[] for i in range(len(arr)): print(arr[i])# Driver CodegenerateGrayarr(3)# This code is contributed# by Mohit kumar 29 |
C#
using System;using System.Collections.Generic;// C# program to generate n-bit Gray codes public class GfG{// This function generates all n bit Gray codes and prints the // generated codes public static void generateGrayarr(int n){ // base case if (n <= 0) { return; } // 'arr' will store all generated codes List<string> arr = new List<string> (); // start with one-bit pattern arr.Add("0"); arr.Add("1"); // Every iteration of this loop generates 2*i codes from previously // generated i codes. int i, j; for (i = 2; i < (1 << n); i = i << 1) { // Enter the previously generated codes again in arr[] in reverse // order. Nor arr[] has double number of codes. for (j = i - 1 ; j >= 0 ; j--) { arr.Add(arr[j]); } // append 0 to the first half for (j = 0 ; j < i ; j++) { arr[j] = "0" + arr[j]; } // append 1 to the second half for (j = i ; j < 2 * i ; j++) { arr[j] = "1" + arr[j]; } } // print contents of arr[] for (i = 0 ; i < arr.Count ; i++) { Console.WriteLine(arr[i]); }}// Driver program to test above function public static void Main(string[] args){ generateGrayarr(3);}} // This code is contributed by Shrikant13 |
Javascript
<script>// Javascript program to generate n-bit Gray codes // This function generates all n bit Gray codes and prints the // generated codes function generateGrayarr(n) { // base case if (n <= 0) return; // 'arr' will store all generated codes let arr = []; // start with one-bit pattern arr.push("0"); arr.push("1"); // Every iteration of this loop generates 2*i codes from previously // generated i codes. let i, j; for (i = 2; i < (1<<n); i = i<<1) { // Enter the previously generated codes again in arr[] in reverse // order. Nor arr[] has double number of codes. for (j = i-1 ; j >= 0 ; j--) arr.push(arr[j]); // append 0 to the first half for (j = 0 ; j < i ; j++) arr[j]= "0" + arr[j]; // append 1 to the second half for (j = i ; j < 2*i ; j++) arr[j]= "1" + arr[j]; } // print contents of arr[] for (i = 0 ; i < arr.length ; i++ ) document.write(arr[i]+"<br>"); } // Driver program to test above function generateGrayarr(3); // This code is contributed by unknown2108</script> |
Output
000 001 011 010 110 111 101 100
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Method 2: Recursive Approach
The idea is to recursively append the bit 0 and 1 each time until the number of bits is not equal to N.
Base Condition: The base case for this problem will be when the value of N = 0 or 1.
If (N == 0)
return {“0”}
if (N == 1)
return {“0”, “1”}
Recursive Condition: Otherwise, for any value greater than 1, recursively generate the gray codes of the N – 1 bits and then for each of the gray code generated add the prefix 0 and 1.
Below is the implementation of the above approach:
C++
// C++ program to generate// n-bit Gray codes#include <bits/stdc++.h>using namespace std;// This function generates all n// bit Gray codes and prints the// generated codesvector<string> generateGray(int n){ // Base case if (n <= 0) return {"0"}; if (n == 1) { return {"0","1"}; } //Recursive case vector<string> recAns= generateGray(n-1); vector<string> mainAns; // Append 0 to the first half for(int i=0;i<recAns.size();i++) { string s=recAns[i]; mainAns.push_back("0"+s); } // Append 1 to the second half for(int i=recAns.size()-1;i>=0;i--) { string s=recAns[i]; mainAns.push_back("1"+s); } return mainAns;}// Function to generate the// Gray code of N bitsvoid generateGrayarr(int n){ vector<string> arr; arr=generateGray(n); // print contents of arr for (int i = 0 ; i < arr.size(); i++ ) cout << arr[i] << endl;}// Driver Codeint main(){ generateGrayarr(3); return 0;} |
Java
// Java program to generate// n-bit Gray codesimport java.io.*;import java.util.*;class GFG{ // This function generates all n // bit Gray codes and prints the // generated codes static ArrayList<String> generateGray(int n) { // Base case if (n <= 0) { ArrayList<String> temp = new ArrayList<String>(){{add("0");}}; return temp; } if(n == 1) { ArrayList<String> temp = new ArrayList<String>(){{add("0");add("1");}}; return temp; } // Recursive case ArrayList<String> recAns = generateGray(n - 1); ArrayList<String> mainAns = new ArrayList<String>(); // Append 0 to the first half for(int i = 0; i < recAns.size(); i++) { String s = recAns.get(i); mainAns.add("0" + s); } // Append 1 to the second half for(int i = recAns.size() - 1; i >= 0; i--) { String s = recAns.get(i); mainAns.add("1" + s); } return mainAns; } // Function to generate the // Gray code of N bits static void generateGrayarr(int n) { ArrayList<String> arr = new ArrayList<String>(); arr = generateGray(n); // print contents of arr for (int i = 0 ; i < arr.size(); i++) { System.out.println(arr.get(i)); } } // Driver Code public static void main (String[] args) { generateGrayarr(3); }}// This code is contributed by rag2127. |
Python3
# Python3 program to generate# n-bit Gray codes# This function generates all n# bit Gray codes and prints the# generated codesdef generateGray(n): # Base case if (n <= 0): return ["0"] if (n == 1): return [ "0", "1" ] # Recursive case recAns = generateGray(n - 1) mainAns = [] # Append 0 to the first half for i in range(len(recAns)): s = recAns[i] mainAns.append("0" + s) # Append 1 to the second half for i in range(len(recAns) - 1, -1, -1): s = recAns[i] mainAns.append("1" + s) return mainAns# Function to generate the# Gray code of N bitsdef generateGrayarr(n): arr = generateGray(n) # Print contents of arr print(*arr, sep = "\n")# Driver CodegenerateGrayarr(3)# This code is contributed by avanitrachhadiya2155 |
C#
// Java program to generate// n-bit Gray codesusing System;using System.Collections.Generic;class GFG { // This function generates all n // bit Gray codes and prints the // generated codes static List<String> generateGray(int n) { // Base case if (n <= 0) { List<String> temp = new List<String>(); temp.Add("0"); return temp; } if (n == 1) { List<String> temp = new List<String>(); temp.Add("0"); temp.Add("1"); return temp; } // Recursive case List<String> recAns = generateGray(n - 1); List<String> mainAns = new List<String>(); // Append 0 to the first half for (int i = 0; i < recAns.Count; i++) { String s = recAns[i]; mainAns.Add("0" + s); } // Append 1 to the second half for (int i = recAns.Count - 1; i >= 0; i--) { String s = recAns[i]; mainAns.Add("1" + s); } return mainAns; } // Function to generate the // Gray code of N bits static void generateGrayarr(int n) { List<String> arr = new List<String>(); arr = generateGray(n); // print contents of arr for (int i = 0; i < arr.Count; i++) { Console.WriteLine(arr[i]); } } // Driver Code public static void Main(String[] args) { generateGrayarr(3); }}// This code is contributed by grand_master. |
Javascript
<script>// Javascript program to generate// n-bit Gray codes// This function generates all n // bit Gray codes and prints the // generated codesfunction generateGray(n){ // Base case if (n <= 0) { let temp =["0"]; return temp; } if(n == 1) { let temp =["0","1"]; return temp; } // Recursive case let recAns = generateGray(n - 1); let mainAns = []; // Append 0 to the first half for(let i = 0; i < recAns.length; i++) { let s = recAns[i]; mainAns.push("0" + s); } // Append 1 to the second half for(let i = recAns.length - 1; i >= 0; i--) { let s = recAns[i]; mainAns.push("1" + s); } return mainAns;}// Function to generate the // Gray code of N bitsfunction generateGrayarr(n){ let arr = []; arr = generateGray(n); // print contents of arr for (let i = 0 ; i < arr.length; i++) { document.write(arr[i]+"<br>"); }}// Driver CodegenerateGrayarr(3);// This code is contributed by ab2127</script> |
Output
000 001 011 010 110 111 101 100
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Method3: (Using bitset)
We should first find binary no from 1 to n and then convert it into string and then print it using substring function of string.
Below is the implementation of the above idea:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;void GreyCode(int n){ // power of 2 for (int i = 0; i < (1 << n); i++) { // Generating the decimal // values of gray code then using // bitset to convert them to binary form int val = (i ^ (i >> 1)); // Using bitset bitset<32> r(val); // Converting to string string s = r.to_string(); cout << s.substr(32 - n) << " "; }}// Driver Codeint main(){ int n; n = 4; // Function call GreyCode(n); return 0;} |
Java
// Java implementation of the above approachimport java.lang.Math;class GFG { static void GreyCode(int n) { // power of 2 for (int i = 0; i < (1 << n); i++) { // Generating the decimal // values of gray code then using // bitset to convert them to binary form int val = (i ^ (i >> 1)); // Converting to binary string String s = Integer.toBinaryString(val); System.out.print( String.format("%1$" + n + "s", s) .replace(' ', '0') + " "); } } // Driver Code public static void main(String[] args) { int n = 4; // Function call GreyCode(n); }}// This code is contributed by phasing17 |
Python3
# Python3 implementation of the above approachdef GreyCode(n): # power of 2 for i in range(1 << n): # Generating the decimal # values of gray code then using # bitset to convert them to binary form val = (i ^ (i >> 1)) # Converting to binary string s = bin(val)[2::] print(s.zfill(n), end = " ")# Driver Coden = 4 # Function callGreyCode(n)# This code is contributed by phasing17 |
Javascript
// JavaScript implementation of the above approachfunction GreyCode(n){ // power of 2 for (var i = 0; i < (1 << n); i++) { // Generating the decimal // values of gray code then using // bitset to convert them to binary form var val = (i ^ (i >> 1)); // Converting to binary string s = val.toString(2); process.stdout.write(s.padStart(4, '0') + " "); }}// Driver Codelet n = 4; // Function callGreyCode(n);// This code is contributed by phasing17 |
C#
// C# implementation of the above approachusing System;class GFG { static void GreyCode(int n) { // power of 2 for (int i = 0; i < (1 << n); i++) { // Generating the decimal // values of gray code then using // bitset to convert them to binary form int val = (i ^ (i >> 1)); // Converting to binary string string s = Convert.ToString(val, 2); Console.Write(s.PadLeft(4, '0') + " "); } } // Driver Code public static void Main(string[] args) { int n = 4; // Function call GreyCode(n); }}// This code is contributed by phasing17 |
Output
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Time Complexity: O(2N)
Auxiliary Space: O(N)
