Check if sum is present in subset of a given array.

#include <iostream>
#define  ll long long int
using namespace std;

int main() {
ll sum,i,req_sum,n,f=0,x;
cin>>n>>req_sum;
ll a[n];
for(i=0;i<n;i++)
cin>>a[i];
x=(1<<n)-1;
for(i=1;i<=x;i++)
{
int b=i;
int j=0;
sum=0;
while(b)
{
int c=b%2;
if(c==1)
{
sum+=a[j];
}
j++;
b=b/2;

}

if(sum==req_sum)
{
f=1;
break;
}

}
if(f==1)
cout<<"Required Sum is Present in Subset of given Set\n";
else
cout<<"Required Sum is not Present in Subset of given Set\n";
// your code goes here
return 0;
}

Check if Linked List is a Palindrome in O(n)

#include <iostream>
using namespace std;
struct node {
char data; //can be integer
node * next;
};

void palindrome(node * head)
{

node * p= head;
node *p1=head;
if(head==NULL)
return ;

//Finding middle element
while(p1!=NULL && p1->next!=NULL)
{

p1=p1->next->next;
p=p->next;
}
//Reversing list from middle element
node *curr=p;
node *prev=NULL;
node *next;
while(curr!=NULL)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
p=prev;

//Comparing two halves of Linked List
node *u=p;
node *t=head;
int f=0;
while(u!=NULL)
{

if(u->data!=t->data)
{
f=1;
break;
}
u=u->next;
t=t->next;
}

if(f==1)
cout<<"No\n";
else
cout<<"Yes\n";
}

int main() {
node *start,*p,*p1,*p2,*p3,*p4;
start=new node;
p=new node ;
p1=new node ;
p2=new node ;
p3=new node ;
p4=new node ;
start->data='a';
p->data='b';
p1->data='c';
p2->data='c';
p3->data='b';
p4->data='a';
start->next=p;
p->next=p1;
p1->next=p2;
p2->next=p3;
p3->next=p4;
p4->next=NULL;
palindrome(start);

return 0;
}

Determine the level of each node in the given tree using bfs

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> a[1000];
int  e,v,vis[1000],level[1000];

int main() {
queue<int> q;
int i,j,k,x,y;
// number of vertices and edges
cin>>v>>e;

for(i=0;i<e;i++)
{
//input all edges of graph
cin>>x>>y;
//for undirected graph
a[x].push_back(y);
a[y].push_back(x);    
}

for(i=0;i<v;i++)
{
vis[i]=0; //Initially mark all vertices unvisited
}
vis[0]=1;
q.push(0);
level[0]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(i=0;i<a[x].size();i++)
{
if(vis[a[x][i]]==0)
{
level[a[x][i]]=level[x]+1;
q.push(a[x][i]);
vis[a[x][i]]=1;
}
}
}
for(i=0;i<v;i++)
{
cout<<i<<"-->"<<level[i]<<"\n";
}
// your code goes here
return 0;
}



Input :
8
7
0 1
0 2
1 3
1 4
1 5
2 6
6 7

Output :

0-->0
1-->1
2-->1
3-->2
4-->2
5-->2
6-->2
7-->3

Find connected components using DFS

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> a[1000];
int  e,v,vis[1000];

void dfs(int n)
{
vis[n]=1;
for(int i=0;i<a[n].size();i++)
{
if(vis[a[n][i]]==0)
dfs(a[n][i]);
}
}

int main() {

int i,j,k,x,y;
// number of vertices and edges
cin>>v>>e;

for(i=0;i<e;i++)
{
//input all edges of graph
cin>>x>>y;
//for undirected graph
a[x].push_back(y);
a[y].push_back(x);    
}

for(i=0;i<v;i++)
vis[i]=0; //Initially mark all vertices unvisited
k=0;  //keep count of connected components
for(i=0;i<v;i++)
{
if(vis[i]==0){
dfs(i);
k++;
}

}

cout<<"Number of  Connected components in graph = "<<k;
// your code goes here
return 0;
}





Input :
6
4
1 2
2 3
1 3
4 5

Output :

Number of Connected components in graph = 3

Sort a stack in ascending order using another stack.

#include <iostream>
#include<stack>
using namespace std;

int main() {
stack<int>s;
s.push(9);
s.push(59);
s.push(2);
s.push(1);
stack<int>s1;
s1.push(s.top());
s.pop();

while(!s.empty())
{
int v=s.top();
s.pop();

while(!s1.empty()&&s1.top()<v)
{
s.push(s1.top());
s1.pop();
}
s1.push(v);


}
s=s1;
while(!s.empty())
{
cout<<s.top()<<"  ";
s.pop();
}

return 0;
}

Get Maximum element of stack at any instance in O(1)

// Print the maximum value in the stack in O(1)

#include<stdio.h>
#include<stack>
#include <iostream>
#include<algorithm>
using namespace std;
#define ll long long int

int main() {

stack<ll> s;
ll n,t,q;
scanf("%lld", &n);
for (int i = 0; i < n; i++) {

 scanf("%lld", &q);
 //q=1 when push element in stack
 //q=2 when pop element from stack
 //q=3 when we have to print maximum element of current stack
if(q==1) // push element to stack (always push maximum element at top)

{
scanf("%lld", &t);
      if (s.empty()) {
           s.push(t);
      }
      else {
          s.push(max(t, s.top()));
      }
}

if(q==2) // pop element from stack
{
      if (!s.empty()) {
s.pop();
      }
}
if(q==3) //Prints maximum element of stack
{
printf("%lld\n", s.top());
}
}
return 0;
}

Basically here we always push the maximum element at top of stack as while pushing element in stack we check if the element to be pushed is greater than top element of stack we push that new element otherwise we push top of stack again thus always maintaining maximum element at the top.

Check Balanced Brackets in a string !!

#include <iostream>

using namespace std;

int s1[10000],top=-1;

void push(int t)

    {

    s1[++top]=t;

}

char pop()

    {

    char x=s1[top--];

    return x;

}

int main(){

    int i,t,f=0;

    cin >> t;

    char x;

       string s;

    for(int a0 = 0; a0 < t; a0++){

         f=0;

        cin >> s;

        top=-1;

    for( i=0;i<s.length();i++)

        {

        if(s[i]=='{'||s[i]=='['||s[i]=='(')

            push(s[i]);

        else{

            

            if(s[i]=='}')

                {

                 x=pop();

                if(x!='{')

                    {

                    f=1;

                    break;

                }

                

            }

            else if(s[i]==']')

                {

                 x=pop();

                if(x!='[')

                    {

                    f=1;

                    break;

                }

            }

            else {

                 x=pop();

         

                if(x!='(')

                    {

                    f=1;

                    break;

                

            }

        }

    }

    }

    if(f==1||(top!=-1))

        cout<<"NO\n";

    else

        cout<<"YES\n";

    }

    

    return 0;

}