Question

Enum Digits {0, 1};

Answer 1

Answer:

The code is given below with appropriate comments for better understanding

Explanation:

#include <bits/stdc++.h>

using namespace std;

enum Digits {

zero,

one

} ;

struct CellType

{

  Digits bit;

  CellType* next;

};

class Minimum

{

public:

  struct CellType* head,*temp; // head to point MSB

  Minimum(string s)

  {

      int sz = s.size(); // binary size as per question it indicates n.

      for(int i=0;i<sz;i++)

      {

          if(s[i] == '0') // if the bit is zero , we add zero at the end of stream

              addAtEnd(zero);

          else // if the bit is one , we one zero at the end of stream

              addAtEnd(one);

      }

      addOne();

      showlist();

  }

  CellType* create(Digits x) // to create a node of CellType*

  {

      CellType* t = new CellType();

      t->bit = x;

      t->next = NULL;

      return t;

  }

  void addAtEnd(Digits x)

  {

     

      if(head == NULL) // if list is empty , then that will be the only node

      {

          CellType* t;

          t = create(x);

          head = temp = t;

      }

      else

      { // other wise we add the node at end indicated by the temp variable

          CellType* t ;

          t = create(x);

          temp->next = t;

          temp=temp->next;

      }

  }

  void showlist()

  {

      // this is just a normla method to show the list

      CellType* t = head;

      while(t!=NULL)

      {

          cout<<t->bit;

          t=t->next;

      }

  }

  void addOne()

  {

      /*

          here since we need to add from the end and it is a singly linked list we take a stack

          and store in last in ,first out format .

          Then we keep on changing all ones to zeroes until we find a zero int he list,

          The moment a zero is found it should be changed to one.

          If everything is one in the sequence , then we add a new zero digit node at the beginning of the list.

      */

      stack<CellType*> st;

      CellType* t = head;

      while(t!=NULL)

      {

          st.push(t);

          t=t->next;

      }

      while(st.size()>0 && (st.top())->bit == one )

      {

          CellType* f = st.top();

          f->bit = zero ;

          st.pop();

      }

      if(st.size())

      {

          CellType* f = st.top();

          f->bit = one ;

      }

      else

      {

          t = create(one);

          t->next = head;

          head = t;

      }

  }

};

int main()

{

  /*

      Here i am taking an integer as input and then converting it to binary using a string varaible s

      if you want to directly take the binary stream as input , remove the comment from "cin>>s" line.

  */

  long long int n,k;

  cin>>n;

  string s;

  k = n;

  while(k>0)

  {

      s = s + (char)(k%2 +48);

      k=k/2;

  }

  reverse(s.begin(),s.end());

  //cin>>s;

  Minimum* g = new Minimum(s);

 

  return 0;

}