SPOJ Q&A

#include<stdio.h>
#define max 100001
#define ull long long int
int pre[max][11];
void presolve()
{
int i,j,temp,k;
for(i=2;i*i<max;i++)
{
if(pre[i][10])
continue;
k=i*i;
for(j=k;j<max;j+=k)
{
if(pre[j][10]==0)
pre[j][10]=1;
}
}

for(i=0;i<max;i++)
{
if(pre[i][10]==0)
{
temp=i;
while(temp)
{
pre[i][temp%10]=1;
temp/=10;
}
}
}
for(i=1;i<max;i++)
{
for(j=0;j<=9;j++)
pre[i][j]+=pre[i-1][j];
}

}

int main()
{
int t,a,b,d;
scanf("%d",&t);
presolve();
while(t--)
{
scanf("%d%d%d",&a,&b,&d);
printf("%d\n",pre[b][d]-pre[a-1][d]);
}
}

Hackerearth QAS

                   Baba & Guruji

Baba wants to kill Guruji. He has a master plan but Guruji is prepared for him.

Baba released a bacterial concentration of 1 unit in Guruji's underground water source on Day 0. The concentration of bacteria becomes xtimes the concentration day before. But,Guruji's powder kills y units of bacteria each day, starting from Day 1.

Guruji needs your help to estimate the concentration of bacteria on the N th day.

Note : Large Input/Output Data. Use fast I/O.

Input :

First line consists of 2 space separated integers x and y. The next line consists of a single integer Q, denoting the number of queries Guruji has for you. The next Q lines are such that each line consists of a single integer N.

Output :

For each query of Guruji, print the number of bacteria present on the N th day on a new line. Since the answer can be really huge, print the answer modulo 1000000007 (10^9 + 7) .

Constraints :

2<=x<=100

0<=y<=(x-2)

1<=Q<=10^6

1<=N<=10^6

1. #include<iostream>
2. #include<cstdio>
3. #include<string>
4. #define ull long long int
5. using namespace std;
6. #define max 1000001
7. #define mod 1000000007
8. ull conc[max];
9. void pre(int x,int y)
10. {
11.  conc[0]=1;
12.  for(int i=1;i<max;i++)
13.     {
14.       conc[i]=(conc[i-1]*x)%mod-y;
15.     }
16. }
17. int main()
18. {
19.     int x,y;
20.     int Q,N;
21.     scanf("%d",&x);
22.     scanf("%d",&y);
23.     scanf("%d",&Q);
24.     pre(x,y);
25.     for(int j=0;j<Q;j++)
26.     {
27.      scanf("%d",&N);
28.      printf("%d\n",conc[N]%mod);
29.     }
30. }

recursion

Base conversion program from decimal

#include<stdio.h>

void convert(int dec,int base)

{

if(dec<base)

{

printf(" %d",dec);

return;

}

int n=dec%base;

convert(dec/base,base);

printf(" %d",n);

}

void main()

{

int dec,base;

printf("Enter the decimal number : ");

scanf("%d",&dec);

        printf("Enter the base : ");

        scanf("%d",&base);

        convert(dec,base);

}

         Printing Digits of a Number

function display prints digit in actual order while the function revdisplay prints the digit in reverse order

#include<stdio.h>

void display(int n)

{

if(n<10)

{

printf(" %d",n);

return;

}

int dig=n%10;

display(n/10);

    printf(" %d",dig);

}

void revdisplay(int n)

{

if(n==0)

{

return;

}

int dig=n%10;

    printf(" %d",dig);

revdisplay(n/10);

}

void main()

{

int num;

printf("Enter the number : ");

scanf("%d",&num);

printf("\nDigits of the number in actual order is : ");

display(num);

printf("\nDigits of the number in reverse order is : ");

revdisplay(num);

}

data structure

Evaluation of Postfix Expression

Algorithm to find the Value of an arithmetic expression P Written in Postfix

[1] Add a right parenthesis ‘)” at the end of P. [This act as delimiter]

[2] Scan P from left to right and repeat Steps 3 and 4 for each element of P until the delimiter “)” is encountered 

[3] If an operand is encountered, put it on STACK

[4] If an operator     is encountered, then

  (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element

  (b) Evaluate B    A

  (c ) Place the result of (b) on STACK

[5] Set Value equal to the top element of STACK

[6] Exit 
example

Evaluation of Prefix Expression

Algorithm to find the Value of an arithmetic expression P Written in Prefix

[1] Scan P from right to left and repeat Steps 2 and 3 for each element of P 

[2] If an operand is encountered, put it on STACK

[3] If an operator  is encountered, then

  (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element

  (b) Evaluate A OP B

  (c ) Place the result of (b) on STACK

[4] Set Value equal to the top element of STACK

[5] Exit 

                 Infix to Postfix

Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix notation

[1] Push “(“ onto STACK and “)” to the end of Q

      [2] Scan Q from Left to Right and Repeat Steps 3 to 6         for each element of Q until the STACK is empty

[3] If an operand is encountered, add it to P

[4] If a left parenthesis is encountered, push it onto STACK

[5] If an operator     is encountered, then:

  (a) Repeatedly pop from STACK and to P each operator (on the top of STACK) which has same precedence as or higher precedence than    .

  (b)  Add     to STACK

[6] If  a right parenthesis is encountered, then

  (a) Repeatedly pop from the STACK and add to P each operator (on top of STACK) until a left parenthesis is encountered.

  (b)  Remove the left parenthesis. [Do not add it to P]

     [7] Exit 

                           Infix to Prefix 

Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent prefix notation

[1] Push “)“ onto STACK and “(” to the begin of Q

      [2] Scan Q from right to left and Repeat Steps 3 to 6         for each element of Q until the STACK is empty

[3] If an operand is encountered, add it to P

[4] If a right parenthesis is encountered, push it onto STACK

[5] If an operator     is encountered, then:

  (a) Repeatedly pop from STACK and to P each operator (on the top of STACK) which has same precedence as or higher precedence than    .

  (b)  Add     to STACK

[6] If  a left parenthesis is encountered, then

  (a) Repeatedly pop from the STACK and add to P each operator (on top of STACK) until a right parenthesis is encountered.

  (b)  Remove the right parenthesis. [Do not add it to P]

     [7] now reverse the expression P we get the prefix expression

data structure programs

Linked list implementation and operations

Linked list operation

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

typedef struct student

{

char name[20];

int roll;

struct student *link;

}student;

student *insbeg(student *head,char *name,int roll)

{

student *temp;

temp=(student *)malloc(sizeof(struct student));

temp->roll=roll;

temp->link=NULL;

strcpy(temp->name,name);

if(head==NULL)

{

head=temp;

   return head;

}

temp->link=head;

head=temp;

return head;

}

student *insatend(student *head,char *name,int roll)

{

student *temp,*p;

temp=(student *)malloc(sizeof(struct student));

temp->roll=roll;

temp->link=NULL;

strcpy(temp->name,name);

if(head==NULL)

{

head=temp;

   return head;

}

p=head;

while(p->link!=NULL)

p=p->link;

p->link=temp;

return head;

}

void search(student *head,char *name,int roll)

{

student *p=head;

int pos=1;

while(p)

{

  if(p->roll==roll && !strcmp(p->name,name))

  {

        printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);

        return ;

  }

  p=p->link;

  pos++;

    }

printf("\nItemp not found");

}

student *insempty(student *head,char *name,int roll)

{

student *temp;

temp=(student *)malloc(sizeof(struct student));

temp->roll=roll;

temp->link=NULL;

strcpy(temp->name,name);

if(head==NULL)

{

head=temp;

   return head;

}

printf("\nlist already contains some data");

return head;

}

void display(student *head)

{

student *p=head;

while(p!=NULL)

{

printf("\nName : %s \tRoll : %d ",p->name,p->roll);

p=p->link;

}

}

student *insertafter(student *head,char *name,int roll,char *nname,int nroll)

{ 

    student *temp,*p=head;

while(p)

{

  if(p->roll==roll && !strcmp(p->name,name))

  {

        printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);

        temp=(student *)malloc(sizeof(struct student));

        temp->roll=nroll;

        temp->link=NULL;

        strcpy(temp->name,nname);

        temp->link=p->link;

        p->link=temp;

        return head;

  }

  p=p->link;

    }

printf("\nItemp not found");

return head;

}

student *insertbefore(student *head,char *name,int roll,char *nname,int nroll)

{ 

    student *temp,*p=head,*q=head;

temp=(student *)malloc(sizeof(struct student));

temp->roll=nroll;

temp->link=NULL;

temp->link=NULL;

strcpy(temp->name,nname);

    if(p->roll==roll && !strcmp(p->name,name))

    {

    printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);

    temp->link=p;

   head=temp;

   return head;

}

while(p)

{

  if(p->roll==roll && !strcmp(p->name,name))

  {

       

        temp->link=p;

        q->link=temp;

        return head;

  }

  q=p;

  p=p->link;

    }

printf("\nItemp not found");

free(temp);

return head;

}

struct student *deletfirst(student *head)

{

student *temp=head;head=head->link;

free(temp);

return head;

}

student *deletbefore(student *head,char *name,int roll)

{

student *p=head,*q=head;

    if(p->roll==roll && !strcmp(p->name,name))

    {

    printf("\nItem is the first node so can't delete ");

   return head;

}

p=head->link;

if(p->roll==roll && !strcmp(p->name,name))

    {

    free(head);

    head=p;

    return head;

}

while(p)

{

  if(p->link->roll==roll && !strcmp(p->link->name,name))

  {

        

        q->link=p->link;

        free(p);

        return head;

  }

  q=p;

  p=p->link;

    }

printf("\nItemp not found");

return head;

}

student *deletafter(student *head,char *name,int roll)

{

student *p=head,*q;

while(p->link)

{

  if(p->roll==roll && !strcmp(p->name,name))

  {

      q=p->link;

        p->link=p->link->link;

        free(q);

        return head;

  }

  p=p->link;

    }

    if(p->roll==roll && !strcmp(p->name,name))

    {

    printf("\nthis is the last item so deletion can't be performed of a node after this");

    return head;

    }

printf("\nItemp not found");

return head;

}

student *deletkey(student *head,char *name,int roll)

{

student *p=head,*q;

    if(p->roll==roll && !strcmp(p->name,name))

    {

    head=p->link;

    free(p);

    return head;

    }

while(p)

{

  if(p->roll==roll && !strcmp(p->name,name))

  {

      q->link=p->link;

        free(p);

        return head;

  }

  q=p;

  p=p->link;

    }

printf("\nItemp not found");

return head;

}

void main()

{

int roll,ch,nroll;

char name[20],nname[20];

student *head=NULL,*p=head;

printf("\n1.insertion at begining\t2.insertion at end\n3.insertion in empty\t4.insertion in between\n5.display\t\t6.search item\t7.insert after item\t8.insert before item\t9.delet first node\t10.delet before\t11.delet after\t12.delet key\t13.exit");

while(1)

{

printf("\nEnter your choice : ");

        scanf("%d",&ch);

switch(ch)

{

   case 1: printf("Enter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=insbeg(head,name,roll);

       break;

   case 2: printf("Enter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=insatend(head,name,roll);

       break;

case 3: printf("Enter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=insempty(head,name,roll);

       break;

case 5: printf("\nContent of list ");

       display(head);

       break;

   case 6: printf("Enter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       search(head,name,roll);

       break;

case 7: printf("After whom \nEnter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       printf("To who\tEnter Name :");

       fflush(stdin);

       gets(nname);

       printf("Enter Roll :");

       scanf("%d",&nroll);

       head=insertafter(head,name,roll,nname,nroll);

       break;

case 8: printf("Before whom \nEnter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       printf("To who\tEnter Name :");

       fflush(stdin);

       gets(nname);

       printf("Enter Roll :");

       scanf("%d",&nroll);

       head=insertbefore(head,name,roll,nname,nroll);

       break;

case 9 :head=deletfirst(head);

       break;

case 10:printf("\nbefore whom");

       printf("\nEnter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=deletbefore(head,name,roll);

       break;

case 11:printf("\nAfter whom");

       printf("\nEnter Name :");

            fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=deletafter(head,name,roll);

       break;

case 12:printf("\nTo whom");

       printf("\nEnter Name :");

           fflush(stdin);

       gets(name);

       printf("Enter Roll :");

       scanf("%d",&roll);

       head=deletkey(head,name,roll);

       break;

case 13: exit(1);

}

}

while(head)

{

p=head->link;

free(head);

head=p;

}

}