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;
}
