{"id":1970,"date":"2020-06-14T15:25:50","date_gmt":"2020-06-14T15:25:50","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1970"},"modified":"2022-03-28T23:53:26","modified_gmt":"2022-03-28T23:53:26","slug":"grey-code","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/grey-code\/","title":{"rendered":"Grey Code"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a non-negative integer n<\/code> representing the total number of bits , we need to print the sequence of gray code. In gray code each consecutive code(binary) differs by only one bit.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to traverse for every bit and for each bit we can either keep it the way it is or flip it (0->1<\/code> or 1->0<\/code>).<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description:<\/h4>\n
\n

We will use backtracking to solve the above problem.
\nBacktracking<\/strong> is the approach to solve the problem by testing all possible answers (by breaking the problems into subproblems). If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
\nFor each bit in the number we have two choices, we can either leave it as it is or toggle it, that way our overall bits has atmost difference of 1<\/code>. We will store the generated value(bits) in a different variable,lets say, ans<\/code>, so for each recursive call the value of ans would be,<\/p>\n

    \n
  • ans<\/code>= previous value<\/li>\n
  • ans<\/code> = new value(inverted bits)<\/li>\n<\/ul>\n

    Suppose if our numer is 3<\/code>, binary representation of 3<\/code> is 0011<\/code>. Now if we fix the last bit and toggle the second last bit 0001<\/code> the difference is of 1<\/code> bit between the actual and the new number.
    \nWe will keep performing above operations each time by decrementing the value, if the value becomes 0<\/code>, we print the generated number .<\/p>\n<\/blockquote>\n

    Algorithm :<\/h3>\n

    gray():<\/h4>\n
      \n
    1. If number == 0<\/code>, print ans<\/code>.<\/li>\n
    2. else, :\n
        \n
      • recursively call, gray(number-1,ans)<\/code>.<\/li>\n
      • toggle the bits in ans<\/code>, ans = flipBits(ans)<\/code>.<\/li>\n
      • recursively call the function with updated ans<\/code>, gray(number-1,ans)<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

        Complexity Analysis :<\/h3>\n
        \n

        In this method each bit has 2<\/code> different choices (either leave the bits unchanged or flip the bits) and we have n<\/code> bits. So the total time complexity<\/strong> is n2n<\/sup> , where n<\/code> is the number of bits.<\/p>\n<\/blockquote>\n

        Solutions:<\/h3>\n\t\t\t\t\t\t