Friday 30 March 2018

Printing all subsets of given string in C/C++

In C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<string>subst;
    string s;
 
    cin>>s;
    int l=s.length();
    for(int i=0;i<l;i++)
    {
        for(int j=1;j<=l-i;j++) // we take substring of length j from index i
            subst.push_back(s.substr(i,j));
    }
 
    sort(subst.begin(),subst.end());  // to sort substrings lexicographically
 
    for(auto t:subst)   //for displaying subsets
        cout<<t<<endl;
 
    return 0;

}
Input:
dab

Output:
a
ab
b
d
da
dab

In C
#include<stdio.h>
#include<string.h>
int main()
{
  char st[100],t[100];
  int i,l,j=0,k;
  scanf("%s",st);
  l=strlen(st);
  for(k=0;k<l;k++)
  {
        for(i=k;i<l;i++)
        {
    t[j++]=st[i];
    t[j]='\0';
    printf("%s\n",t);
        }
        j=0;
    }

    return 0;
}

Input:
abcd

Output:
a
ab
abc
abcd
b
bc
bcd
c
cd
d

Sunday 25 March 2018

Segment trees range maximum query: Finding maximum element in given range

Segment Tree: 


Program:


#include <iostream>
#include <vector>
using namespace std;
const int M = 100000; // maximum size of input array
vector<long> v(M), tree(M * 4); // allocating size for segment tree and array
void build(long node, long a, long b) // to construct segment tree
{
 if (a > b) 
     return;
 if (a == b) 
 {
  tree[node] = v[a];
  return;
 }
 build(node * 2 + 1, a, (a + b) / 2);
 build(node * 2 + 2, (a + b) / 2 + 1, b);
 if (tree[node * 2 + 1] > tree[node * 2 + 2])
  tree[node] = tree[node * 2 + 1];
 
 else
  tree[node] = tree[node * 2 + 2];
}
void update(long node, long a, long b, long x, long y) // to update segment tree
{
 if (a > b) 
     return;
 if (a == b) {
  v[x] = y;
  tree[node] = y;
 }
 else
 {
  long mid = (a + b) / 2;
  if (x <= mid) update(node * 2 + 1, a, mid, x, y);
  else update(node * 2 + 2, mid + 1, b, x, y);
  if (tree[node * 2 + 1] > tree[node * 2 + 2])
   tree[node]= tree[node * 2 + 1];
  else 
   tree[node] = tree[node * 2 + 2];
 }
}
long query(long node, long a, long b, long l, long r) // to query segment tree 
{
 if (a > b || a > r || b < l)
 {
  long temp;
  temp = -9223372036854775807;
  return temp;
 }
 if (a >= l && b <= r) 
     return tree[node];
 long p1 = query(node * 2 + 1, a, (a + b) / 2, l, r);
 long p2 = query(node * 2 + 2, (a + b) / 2 + 1, b, l, r);
 if (p1 > p2) 
     return p1;
 else 
     return p2;
}
int main() 
{
 long n, q, l, r, i, x, y, ch;
 cin >> n >> q;                  // reading number of elements and number of queries
 for (i = 0; i < n; i++) 
  cin >> v[i];                // reading input array

 build(0, 0, n - 1);

 while (q--) 
 {
  cin >> ch;
  if (ch == 1)
  {
   cin >> x >> y;
   update(0, 0, n - 1, x, y);
  }
  else
  {
   cin >> l >> r;
   cout<<query(0,0,n-1,l,r);
  }
 }
return 0;
}

Input :

6             --number of array elements

3             --number of queries

-2  4  2  -1  7  5             array elements


2 0 3       -maximum element in index between 0 and 3

1 4 2       -update 4th index element to 2

2 0 5       -maximum element in index between 0 and 5


Output:45

=========================================================================

Problem: http://codeforces.com/problemset/problem/339/D

Solution using Segment trees: 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int M = 131073;
vector<long> v(M);
vector<pair<long, long>> tree(M * 4);
void build(long node, long a, long b) {
 if (a > b) return;
 if (a == b) 
 {
  tree[node].first = v[a];
  tree[node].second=1;
  return;
 }
 build(node * 2 + 1, a, (a + b) / 2);
 build(node * 2 + 2, (a + b) / 2 + 1, b);
 tree[node].second = tree[2*node+1].second+1;
 if (tree[node].second&1)
  tree[node].first = tree[node * 2 + 1].first ^ tree[node * 2 + 2].first;
 else
     tree[node].first = tree[node * 2 + 1].first | tree[node * 2 + 2].first;
}
void update(long node, long a, long b, long x, long y) 
{
 if (a > b)
     return;
 if (a == b)
 {
  tree[node].first = y;
 }
 else 
 {
  long mid = (a + b) / 2;
  if (a<=x && x <= mid) 
      update(node * 2 + 1, a, mid, x, y);
  else 
      update(node * 2 + 2, mid + 1, b, x, y);
  if (tree[node].second&1)
      tree[node].first = tree[node * 2 + 1].first ^ tree[node * 2 + 2].first;
     else
         tree[node].first = tree[node * 2 + 1].first | tree[node * 2 + 2].first;
 }
}

int main() 
{
 long n, q, l, r, i, x, y, ch;
 cin >> n >> q;
 n=pow(2,n);
 for (i = 0; i < n; i++) 
  cin >> v[i];
 build(0, 0, n - 1);
 
 while (q--) 
 {
  cin >> x >> y;
  update(0, 0, n - 1, x - 1, y);
  cout<<tree[0].first<<endl;
 
 }
return 0;
}
service lane problem in hacker rank

Monday 19 March 2018

Mo's Algorithm

In Mos algorithm, we sort the queries
For ex:
Input : The following are Queries. The starting indices and ending indices are as follows

2 4
6 8
0 2
3 5
2 3

Output: After Sorting the Queries become as shown below.  
0 2
2 3
2 4
3 5
6 8


Since There are 9 elements. Square root of 9 is 3. Hence the Block Size is 3

indices 0,1,2 belong to first block where first block stores sum of the elements at these indices. In Mo's algorithm, the result of previous query is used in the calculation of next query

=========================================================================================================================

Mos algorithm to solve range sum queries

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int bs=174;//block_size is 174 if n can take maximum of 30010
struct query
{
  int l,r,index;
};

bool cmp(query f,query s)//acts just like group by in SQL
{
    if(f.l/bs != s.l/bs) //if they dont belong to same block as l/bs gives block number 
        return f.l/bs < s.l/bs;
    return f.r<s.r; // same block sort by r value
}

int main() 
{
  int a[] ={1,5,2,4,6,1,3,5,7},n=9;  
  bs=sqrt(n); //block_size
  int noq,ad,b_id;
  cin>>noq;
  struct query q[noq];
  for(int k=0;k<noq; k++)
{
      scanf("%d%d",&q[k].l,&q[k].r);
      q[k].index=k;
  }
    // l--;r--;     
  sort(q,q+noq,cmp);
  int sum=0,cr=0,cl=0,ans[noq];
  for(int i=0;i<noq;i++)
  {
    int left=q[i].l,right=q[i].r;
    while(cl<left)
    {
        sum=sum-a[cl];
        cl++;
    }
    while(cl>left)
    {
        sum=sum+a[cl];
        cl--;
    }
    while(cr<=right)
    {
        sum=sum+a[cr];
        cr++;
    }
    while(cr>right+1)
    {
        sum=sum-a[cr-1];
        cr--;    
    }
    ans[q[i].index]=sum;
   // cout<<sum<<endl;
  
  }
  for(int i=0;i<noq;i++)
        cout<<ans[i]<<endl;
  return 0;
}

input:
5
2 4
6 8
0 2
3 5
2 3

output:
12
15
8
11
6



Saturday 17 March 2018

Square Root Decomposition to Solve Sum of array elements Range Queries in Competitive Programming

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

int main() {
  int a[] ={1,5,2,4,6,1,3,5,7},n=9;  
  int bs=sqrt(n); //block_size
  int nob=ceil((double)n/bs);//number of blocks
  int res[nob],j=0,sum; //res array stores the block sum
  //printf("%d",nob);
  for(int i=0;i<nob;i++)
  {
      sum=0;
      for(int c=0;c<bs;c++,j++)
        sum=sum+a[j];
      res[i]=sum;  //updating block sum
  }
 //for(int i=0;i<nob;i++)
 //cout<<res[i]<<" ";
  int noq,ad,b_id;
  cin>>noq;
  while(noq--)
  {
      int l,r,opt;
      cin>>opt>>l>>r;
    // l--;r--;     
      switch(opt)
      {
          case 1: b_id=l/bs;
                  res[b_id]=res[b_id]-a[l]+r;
                  a[l]=r;
                  break;
          case 2:  ad=0;
                    while(l<r && l%bs != 0 && l!=0 ){
                        ad=ad+a[l];l++;}

                     while(l+bs-1<=r)
                    {
                        ad=ad+res[l/bs];  //l/bs will give the block index
                        l=l+bs;
                        // cout<<ad<<endl;
                    }
                    for(;l<=r;l++)
                        ad=ad+a[l];
                     cout<<ad<<endl;
      }

 }
  return 0;
}

Thursday 15 March 2018

Pattern Programs in C



Write a program to print the above pattern

#include <stdio.h>

int main()
{
    int r,c, n,nr,nc,c1=1,c2=1;
    scanf("%d", &n);
    nr=2*n-1;
    nc=2*n-1;
    for(r=1;r<=nr;r++)
    {
        for(c=1;c<=nc;c++)
        {
            if(c<c1||c>c2)
                printf(" ");
            else
                printf("*");
        }
        if(r<n)
        {
            c1++;
            c2=c2+2;
        }
        else
        {
            c1--;
            c2=c2-2;
        }
        printf("\n");
    }
}

==================================================

http://chitranshugupta.blogspot.com/p/c.html#pt6 

/* Write a Program to print Butterfly Matrix Pattern  
   *       *
   **     **
   ***   ***
   **** ****
   *********
   **** ****
   ***   ***
   **     **
   *       *
*/
 
       int main()
       {
              int n=5;//No. of rows
              int i=1;
              int c1=1;
              int c2=2*n-1;
  
              int j=n+1;
              int b1=n;
              int b2=n;

              for(int row=1;row<=(2*n-1);row++)
              { 
  
                      for(int col=1;col<=(2*n-1);col++)
                      { 
                                 if((row==i && col >c1 && col< c2) || (row==j && col >=b1 && col<=b2))
                                                printf(" ");      
                                 else
                                                printf("*");
                      } 
                      if(row< n)
                      {
                           i++;
                           c1++;
                           c2--;
                      } 
                      else if(row >n)
                      {
                           j++;
                           b1--;
                           b2++;
                      }
                      printf("\n");
              }
             return 0;
       }


Write a C program to print the following number pattern



#include <stdio.h>
main()
{
int n,i,j,k,spaces,prints,c;
scanf("%d",&n);
spaces = n-1;
prints = 1;
for(i=1;i<=2*n-1;i++)
{
for(j=1;j<=spaces;j++)
printf("   ");
c=1;
for(k=1;k<= 2*prints -1; k++)
{
printf("%3d",c);
if(c<n)
c++;
else
c--;
}
if(i<n)
{
spaces--;
prints++;
}
else
{
spaces++;
prints--;
}
printf("\n");
}
}
====================================================================
Write a C program to print the following pattern in C


#include <stdio.h>
main()
{
int n,i,j,k,l;
scanf("%d",&n);
int n1=2*n-1;
int t=n1/2,c=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=t;j++)
printf("*");
for(k=1;k<=c;k++)
printf(" ");
for(;j<=(n1-c);j++)
printf("*");
if(c == 0)
c=c+1;
else
{
c=c+2;
t=t-1;
}
printf("\n");
}
}
===================================================================
Write a C program to print the following pattern




Program:
#include <stdio.h>
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
main()
{
    int n,i,j,l;
    scanf("%d",&n);
    l=2*n+1;
    for(i=0;i<l;i++){
        for(j=0;j<l;j++)
            printf("%d",max(abs(n-i),abs(n-j)));
        printf("\n");
    }
}




Write a C program to print the following pattern

                    1
              1    2
         4   3    9


#include<stdio.h>
main()
{
int n,c=1,flag=1,i,j,k;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=n-1;j>i;j--)
{
printf("   ");
}
for(k=0;k<=i;k++)
{
if(flag){
printf("%3d",c);flag=0;}
else{
printf("%3d",c*c);flag=1;
c++;
}
}
printf("\n");
}
}


========================================================================

1
1          1
2          1
1          2          1          1
1          1          1          2          2          1

in the above pattern for example n= 1211
1          2          1          1
units and tens place digits are same digit ‘1’ and count =2 ,j =1, n1 =0
so n1= (10*count+same_digit)*j +n1
n1=(10*2+1)*1+0=21
and n becomes 12 i.e, n =12
in 12, units and tens place digit are not same. digit 2 occurs once so count =1 , j=100 , n1=21
n1 = (10*1+2)*100+21 = 1221
now n =1
1 occurs only once so count = 1, j= 10000,n1=1221
n1=(10*1+1)*10000+1221
n1 = 11*10000+1221= 111221
#include <stdio.h>
int main()
{
            int i,n=1,j,n1,temp,c,rows;
            printf("enter number of rows\n");
            scanf("%d",&rows);
            for(i=0;i<rows;i++)
            {
                        n1=0;
                        j=1;
                        printf("%d\n",n);
                        while(n)
                        {
                                    temp=n%10;
                                    n=n/10;
                                    c=1;
                                    while(temp == n%10)   // number of digits same starting from units place
                                    {
                                               c++;
                                               n=n/10;
                                    }
                                    n1=(((10*c)+temp)*j)+n1;   
                                    j=j*100;
                        }
                        n=n1;
            }
            return 0;
}





============================================
to print
*
*   *
*   *    *

in first line, we print one * and
in second line, we print  * * (2 stars) and
in third line, we print * * * (3 stars) and
as i is giving the line number,so j runs i times. 
to print i *'s in ith line

========================================
n=4
* * * *

* * * *

* * * *

* * * *
in first line, we print * * * * (n stars) and in second line, we print   * * * * (n stars) and in third line, we print * * * * (n stars) and so j runs n times. to print n *'s in each line