Movie Theatre Madness

problem statement is here

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct compare
{
  bool operator()(const long long & l, const long long & r)
  {
      return l > r;
  }
};

int main(){
priority_queue<long long,vector<long long>, compare > pq;
int n,i,a;
long long ar[100005],max=1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<n;i++){
pq.push(ar[i]);
while(1){
if(pq.top()==ar[i]){
break;
}else{
max=(max*(ar[i]))%1000000007;
pq.pop();
}
}
}
max=max%1000000007;
printf("%lld\n",max);

return 0;
}

Pattern Find

problem statement is here

it is a basic concept of KMP algorithm

if u want to read about KMP algorithm u can find it here

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

int zr[1000002],q;

void computeLPSArray(char *pat, int M, int *lps){

    int len=0,i=1;

    lps[0]=0;

    while (i < M){

       if (pat[i] == pat[len]){

         len++;

         lps[i] = len;

         i++;

       }else{

         if (len != 0){

           len = lps[len-1];

         }else{

           lps[i] = 0;

           i++;

         }

       }

    }

}

void KMPSearch(char *pat, char *txt){

    int M = strlen(pat);

    int N = strlen(txt);

    int *lps = (int *)malloc(sizeof(int)*M);

    int j=0,i=0; 

    computeLPSArray(pat, M, lps);

    while (i < N){

      if(pat[j] == txt[i]){

        j++;

        i++;

      }

   if (j == M){

        zr[q++]=i-j+1;

        j = lps[j-1];

      }else if (i < N && pat[j] != txt[i]){

        if (j != 0)

         j = lps[j-1];

        else

         i = i+1;

      }

    }

    free(lps);

}

int main(){

   int t,i;

   scanf("%d",&t);

   while(t--){

    q=0;

    char ar[1000006],br[1000005];

    scanf("%s %s",ar,br);

    KMPSearch(br,ar);

    if(q==0){

    printf("Not Found\n");

    }else{

    printf("%d\n",q);

    for(i=0;i<q;i++){

    printf("%d ",zr[i]);

    }

    printf("\n");

    }

   }

   return 0;

}

How to Handle the Fans

problem statement is here

#include<stdio.h>
#include<string.h>
long long n,br[1000000]={0};
long long int add(long long i,long long b){
while(i<=n){
br[i]+=b;
i=i+(i&((-1)*i));
}
}
long long find(long long i){
long long s=0;
while(i>0){
s+=br[i];
i=i-(i&((-1)*i));
}
return s;
}
int main(){
char ar[100];
long long a,b,c,d,i,j,t,u=0,ans,q;
scanf("%lld %lld",&n,&q);
while(q--){
scanf("%s %lld %lld",ar,&a,&b);
if(ar[0]=='a'){
add(a,b);
}else if(ar[0]=='f'){
if(a>1)
d=find(b)-find(a-1);
else
d=find(b);
printf("%lld\n",d);
}
}
return 0;
}

Breadth first traversal for undirected graph

here we are assuming that all the nodes are connected


#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
void bfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  queue<int> que;
  visited[i]=1;
  que.push(i);
  while(que.size()>0){
   i=que.front();
   que.pop();
   printf("%d\n",i);
   for(j=0;j<ar[i].size();j++){
          if(visited[ar[i][j]]==0){
              que.push(ar[i][j]);
              visited[ar[i][j]]=1;
          }
      }
  }

}
int main(){
  int a,b,i,j,n,m;
  printf("no of nodes\n");
  scanf("%d",&n);
  vector<int> ar[n+9];
  int visited[n+9];
  for(i=0;i<n+9;i++){
    visited[i]=0;
   }
   printf("no of edges\n");
   scanf("%d",&m);
   printf("Enter edges\n");
   for(j=0;j<m;j++){
     scanf("%d %d",&a,&b);
     ar[a].push_back(b);
     ar[b].push_back(a);
   }
   printf("from which node to traverse\n");
   scanf("%d",&i);
   bfs(ar,visited,i,n);
  return 0;
}

Minimum spanning tree kruskal algorithm

Time complexity O(eLoge + eLogv)
steps:-
        sort all the edges according to their weights
        pick minimum weighted edge and check for cycle
                     if(makes cycle) -> discard that edge
                     else -> take it
        repeat it until we get  v-1 nodes 

no of edges in final tree = v-1


#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int e,v;
struct nodes{
int a;
int b;
int w;
};
struct checker{
int parent;
int rank;
};

bool compare (nodes p1, nodes p2){
return (p1.w > p2.w);
}

int find( struct checker br[], int i){
    if (br[i].parent != i){
    br[i].parent = find(br, br[i].parent);
    }
  return br[i].parent;
}

void Union(struct checker br[],int x,int y){
    int xroot = find(br, x);
    int yroot = find(br, y);
    if (br[xroot].rank < br[yroot].rank){
    br[xroot].parent = yroot;
    }else if (br[xroot].rank > br[yroot].rank){
    br[yroot].parent = xroot;
    }else{
        br[yroot].parent = xroot;
        br[xroot].rank++;
    }
}
int kruskal(vector<nodes>& ar){
int weight=0;
struct checker br[1000];
int i;
sort(ar.begin(),ar.end(),compare);
for(i=0;i<v;i++){
br[i].parent=i;
br[i].rank=0;
}
int z=0;
for(i=e-1;i>=0;i--){
int x=find(br,ar[i].a);
int y=find(br,ar[i].b);
if(x!=y){
Union(br,ar[i].a,ar[i].b);
weight+=ar[i].w;
z++;
}
if(z==v-1){
break;
}
}
return weight;
}

int main(){
int c,d,r,i,j,n,m;
vector<nodes> ar(1000);
        printf("Enter no of vertexes and edges\n");
scanf("%d %d",&v,&e);
        printf("Edges\n");
for(i=0;i<e;i++){
scanf("%d %d %d",&ar[i].a,&ar[i].b,&ar[i].w);
}
c=kruskal(ar);
printf("%d\n",c);
return 0;
}

Dijkstra’s algorithm using adjacency matrix

this program finds distance of all vertexes from a given source vertex
time complexity using adjacency matrix is O(v^2)
it doesn't work for negative weighted graphs


#include <stdio.h>
#include <limits.h>
int n;
int takemin(int dist[],int visited[]){
   int min=INT_MAX,min_index,i;
  for(i=0;i<n;i++)
     if(visited[i]==0 && dist[i] <= min){
      min=dist[i];
min_index=i;
     }
  return min_index;
}

int printfinal(int dist[],int n){
int i;
   printf("Vertex   Distance from Source\n");
   for(i=0;i<n;i++)
      printf("%d                 %d\n",i,dist[i]);
}

void dijkstra(int graph[n][n], int source){
     int dist[n],visited[n],i,j,u;
     for(i=0;i<n;i++){
      dist[i]=INT_MAX;
visited[i]=0;
     }
     //taking distance of source as 0
    dist[source]=0;
    for(j=0;j<n-1;j++){
       //take min distance vertex which is not taken yet
       u=takemin(dist,visited);
  //mark the picked vertex as visited
       visited[u]=1;
//update the distances of vertexes adjacent to the picked vertex
       for(i=0;i<n;i++){
        if(graph[u][i]>0 && visited[i]==0){
        if(dist[u]+graph[u][i]<dist[i] || dist[i]==INT_MAX){
        dist[i]=dist[u]+graph[u][i];
        }
        }
    }
    }
    printfinal(dist,n);
}

int main(){
int i,j;
printf("Enter no of vertexes\n");
scanf("%d",&n);
int graph[n][n];
printf("Enter adjacency matrix\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&graph[i][j]);
}
}
  dijkstra(graph, 0);
  return 0;
}

dfs traversal of a graph using adjacency list

#include<stdio.h>
#include<vector>
using namespace std;
void dfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  visited[i]=1;
  printf("%d\n",i);
  for(j=0;j<ar[i].size();j++){
  if(visited[ar[i][j]]==0){
  dfs(ar,visited,ar[i][j],n);
  }
  }
}
int main(){
  int a,b,i,j,n,m;
  printf("no of nodes\n");
  scanf("%d",&n);
  vector<int> ar[n+9];
  int visited[n+9];
  for(i=0;i<n+9;i++){
  visited[i]=0;
  }
  printf("no of edges\n");
  scanf("%d",&m);
  for(j=0;j<m;j++){
    scanf("%d %d",&a,&b);
    ar[a].push_back(b);
    ar[b].push_back(a);
  }
  for(i=1;i<=n;i++){
  if(visited[i]==0){
    dfs(ar,visited,i,n);
  }
  }
  return 0;
}

dfs traversal of a graph using adjacency matrix

// complexity O(V+E)

#include<stdio.h>
int ar[100][100];
void dfs(int visited[],int i,int n){
int j;
visited[i]=1;
printf("%d\n",i);
for(j=0;j<n;j++){
if(ar[i][j]==1 && visited[j]!=1){
dfs(visited,j,n);
}
}
}
int main(){
int a,b,i,j,n,visited[101];
printf("Enter no of vertices\n");
scanf("%d",&n);
printf("Enter adjacency matrix\n");
for(i=0;i<n;i++){
visited[i]=0;
for(j=0;j<n;j++){
scanf("%d",&ar[i][j]);
}
}
for(i=0;i<n;i++){
if(visited[i]==0){
dfs(visited,i,n);
}
}
return 0;
}