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

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;

}

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

C function to check whether a given number is prime or not

int prime(unsigned long long p)
{
    unsigned long long int i;
     if (p <= 1)  return 0;
    if (p <= 3)  return 1;
    if (p%2 == 0 || p%3 == 0) return 0;long int l=sqrt(p);
    for ( i=5; i<=l;i=i+6)
        if (p%i == 0 || p%(i+2)==0)
           return 0;

    return 1;
}

Space Less Hacker Rank Solution in C++

https://www.hackerrank.com/contests/ccollesium/challenges/space-less

solution:

#include <bits/stdc++.h>

using namespace std;
int main(void)
{

   int t;
   cin>>t;
   while(t--)
   {
        int num,c=0;
        string k;
        cin>>num;
     cin>>k;
        char st[1000000]={0};
        int n = 0;
        for (int i = 1; i <= num; i++)
            n += sprintf (&st[n], "%d", i); // sprintf returns the number of characters written
        string s(st);                       // converting a character array to string
        //the data typt for f must be size_t since we used find
        for(size_t f = 0 ;(f = s.find( k, f )) < n; f++) // we can use string::npos instead of n to loop until the end of the string".
            c++;
        cout<<c<<endl;  
   }
    return 0;
}

Printing all occurrence (indexes) of a particular character in a string in c++

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string st="mississipi";

vector<char>s;

copy(st.begin(),st.end(),back_inserter(s)); // converting string to vector

s.push_back('\0');       //  converting string to vector

vector<char>::iterator it=s.begin();

int i=-1;

while(1){

    

it=find(s.begin()+i+1,s.end(),'s'); //once we find first 's' reduce the search range

if(it == s.end())

        break;

i=it-s.begin();  // storing index of the occurrence of 's' in string 

cout<<i;

}

return 0;

}