ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

You are given a positive number “n”, print the sequence of grey code solution in CPP

prodevelopertutorial September 9, 2018

 

Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

Before solving this problem, let us understand what grey code is.

Before knowing about grey code, we shall understand about the binary format.

Below are some numbers and their binary representation:

0     000

1      001

2     010

3      011

4     100

5     101

6     110

7     111

If we check the difference in bits between 2 consecutive number will be as follows:

The difference in bits between 0 and 1 is 1. Because only leftmost bit is changed.

The difference in bits between 1 and 2 is 2. Because 2nd digit changed from 0 to 1 and the third digit is changed from 1 to 0.

Similarly, the difference in bits between 3 and 4 is 3. Because all the 3 digits have been changed.

In a computer this is a problem, hence we use the grey code system. In the grey code system, the difference between any 2 consecutive numbers will always be 1.

So to write grey code, we start with 000.

000

001

011

010

110

111

101

100

In the above list, the difference between any 2 consecutive digits is only 1 bit difference.

Hence according to our question, “n” represents the number of bits in the code.

For n = 2, the grey code can be written as below:

As grey code starts from 00,

00

01

11

10

If we convert them into the decimal format, it will be [0, 1, 3, 2]. Hence the solution.

To get the grey code of Nth element, we use below formula:

N ^ floor(N/2)

Solution in C++

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;


std::vector<int> get_grey_code(int n) 
{
	
	vector <int> result;

	if (n == 0) 
	{
		result.push_back(0);
		return result;
	}

	for (int i = 0; i < pow(2, n); i++) 
	{
		result.push_back(i ^ (i / 2));
	}

	return result;

}

int main()
{

	int n = 2;
	vector<int> result = get_grey_code( n );

	for (int i = 0; i < result.size(); ++i)
	{
		cout<< " "<< result[i]<<endl;
	}
}

Output:

 0
 1
 3
 2

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io