FACTORIAL LENGTH

5917. Factorial length

Problem code: LENGFACT


Q.) FIND THE LENGTH OF FACTORIAL.

SOLUTION---




#include<stdio.h>
#include<math.h>
int main()
{
int t;
long long int  ans,n;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%lld",&n);
if(n<3)
printf("1\n");
else{
ans=ceil(log10(2*3.141592653589793*n)/2 + n*log10(n/2.7182818284590452353));
printf("%lld\n",ans);
}
}
return 0;
}

9734. Hacking the random number generator SPOJ

9734. Hacking the random number generator

Problem code: HACKRNDM




#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    signed int n,k,count=0,i;
    scanf("%u %u",&n,&k);
    signed int arr[n];
    for(i=0;i<n;i++)
        scanf("%u",&arr[i]);
    sort(arr,arr+n);
    for(i=0;i<n;i++)
    {
        int flag=0,mid;
        //binary search//
        int lb=0,ub=n-1;
        while(lb<=ub)
        {
            mid=(lb+ub)/2;
            if(arr[mid]==arr[i]+k)
            {
                flag=1;
                break;
            }
            else if(arr[mid]>arr[i]+k)
                ub=mid-1;
            else
                lb=mid+1;
        }
        if(flag==1)
            count+=1;
    }
    printf("%u\n",count);
    return 0;
}

5976 Traversing Grid SPOJ

5976. Traversing Grid

Problem code: TRGRID



#include<stdio.h>
int main()
{
    long long int n,m;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&n,&m);
        if(n%2==0&&m%2==0)
        {
            if(n>m)
                printf("U\n");
            else if(m>=n)
                    printf("L\n");
        }
        else if(n%2!=0&&m%2!=0)
        {
            if(n>m)
                printf("D\n");
            else if(m>=n)
                printf("R\n");
        }
        else
        {
            if(n%2==0&&m%2!=0)
                {
                    if(n>m)
                        printf("D\n");
                    else
                        printf("L\n");
                }
            if(n%2!=0&&m%2==0)
                {
                    if(n<m)
                        printf("R\n");
                    else
                        printf("U\n");
                }
        }
    }
    return 0;
}

SORT THE ARRAY CONTAINING ONLY 0's AND 1's

Q.) SORT THE ARRAY CONTAINING ONLY 0's AND 1's .

SOLUTION--


#include<stdio.h>
void swap(int *x,int *y)
{
        int temp;
        temp=*x;
        *x=*y;
        *y=temp;
        //return 0;
}
int main()
{
        int num,i,j;
        scanf("%d",&num);
        int arr[num];
        for(i=0;i<num;i++)
                scanf("%d",&arr[i]);
        for(i=0,j=num-1;i<=j;)
        {
                if(arr[i]==0)
                        i++;
                else{
                if(arr[j]==0)
                        swap(&arr[i],&arr[j]);
                j--;
                }
        }
        for(i=0;i<num;i++)
                printf("%d ",arr[i]);
        return 0;
}

REMOVE THE DUPLICATES FROM A STRING

Q.) REMOVE THE DUPLICATES FROM A STRING WITH O(N).

SOLUTION---


#include<stdio.h>
#include<string.h>
int main()
{
    char str[400];
    scanf("%s",str);
    int arr[128];
    int i,d,len;
    for(i=0;i<128;i++)
        arr[i]=0;
    len=strlen(str);
    for(i=0;i<len;i++)
    {
         d=str[i];
        arr[d]+=1;
    }
    for(i=0;i<len;i++)
    {
        d=str[i];
        if(arr[d]!=0)
        {
            printf("%c",str[i]);
            arr[d]=0;
        }
    }
    return 0;
}

UNIQUE CHAR IN STRING

Q.) FIND UNIQUE CHAR IN  A GIVEN STRING.

SOLUTION---


#include<stdio.h>
#include<string.h>
int main()
{
    char str[400];
    scanf("%s",str);
    int i,d,len;
    len=strlen(str);
    int arr[128];
    for(i=0;i<128;i++)
        arr[i]=0;
    for(i=0;i<len;i++)
    {
        d=str[i];
        arr[d]+=1;
    }
    for(i=0;i<len;i++)
    {
        d=str[i];
        if(arr[d]==1){
            printf("%c ->unique char in string",str[i]);
           
        }
    }
    return 0;
}

MERGE TWO ARRAY IN SORTED ORDER

Q.) GIVEN TWO SORTED ARRAY MERGE THEM IN A SHORTED ARRAY .
TEST CASES

ARRAY 1 -> -10 12 100 141 240 

ARRAY 2-> -20 10 12 150 300 500 1932 

OUTPUT ARRAY -> -20 -10 10 12 12 100 141 150 240 300 500 1932

(ASKED IN AMAZON INTERVIEW)

#include
int main()
{
    int size_1,size_2,i;
    //enter the size of two ordered array//
    scanf("%d %d",&size_1,&size_2);
    int arr1[size_1],arr2[size_2],arr[size_1+size_2];
    //enter values in arr1//
    for(i=0;i<size_1;i++)
        scanf("%d",&arr1[i]);
    //enter values in arr2//
    for(i=0;i<size_2;i++)
        scanf("%d",&arr2[i]);
    int num_1=0,num_2=0;
    for(i=0;i<size_1+size_2;i++)
    {
        if(arr1[num_1]>arr2[num_2]&&num_2<size_2)
        {
            arr[i]=arr2[num_2];
            num_2=num_2+1;

        }
        else
        {
            arr[i]=arr1[num_1];
            num_1=num_1+1;
        }
    }
    // merged shorted array //
    for(i=0;i<size_1+size_2;i++)
        printf("%d ",arr[i]);
    return 0;
}

The Indian Connection SPOJ

11402. The Indian Connection

Problem code: DCEPC504



Input:
4
1 1
2 1
2 2
4 5 
Output:
Male
Male
Female
Female

solution---


this question is related to THUE MORSE series.
sequence http://oeis.org/A010060

how to create THUE MORSE series--

a(2n)=a(n)
a(2n+1)=1-a(n)

let for n=0,a(0)=0;



n = 0, substituting in Eq. 1: t1 = 1 - t0 = 1 (t0 is 0)
n = 1, substituting in Eq. 2: t2 = t1 = 1
n = 1, substituting in Eq. 1: t3 = 1 - t2 = 1 - 1 = 0
n = 2, substituting in Eq. 2: t4 = t2 = 1
n = 2, substituting in Eq. 1: t5 = 1 - t4 = 1 - 1 = 0
n = 3, substituting in Eq. 2: t6 = t3 = 0
n = 3, substituting in Eq. 1: t7 = 1 - t6 = 1 - 0 = 1


HERE is the code

#include
int main()
{
    int t,count;
    long long int k,num;
    scanf("%d",&t);
    while(t--)
    {
        count=0;
        scanf("%lld %lld",&k,&num);
        if(num==1)
            printf("Male\n");
        else if(num==2)
            printf("Female\n");
        else{
            num=num-1;
        while(num>1)
        {
            if(num%2!=0)
                count+=1;
            num=num/2;
        }
        if(count%2==0)
            printf("Female\n");
        else
            printf("Male\n");
        }
        printf("\n");
    }
    return 0;
}

Onotole needs your help SPOJ

7742. Onotole needs your help

Problem code: OLOLO






#include<stdio.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    long long int arr[n];
    for(i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    long long int a,ans;
    a=arr[0];
    for(i=1;i<n;i++)
    {
        ans=a^arr[i];
        a=ans;
    }
    printf("%lld\n",ans);
    return 0;
}


/* HERE a is a variable having value at position zero and the then there is a variable which is equal to X-OR of element a and arr[i] and then we assign value of ans in variable a. 


if you find any bugs or more efficient solution than this than post in comments.

IMPLEMENTATION OF PRIORITY QUEUE USING ARRAY

IMPLEMENTATION OF PRIORITY QUEUE USING ARRAY 


#define SIZE 5            /* Size of Queue */
int PQ[SIZE],f=0,r=-1;       /* Global declarations */

PQinsert(int elem)
{
    int i;       /* Function for Insert operation */
    if( Qfull()) printf("\n\n Overflow!!!!\n\n");
    else
    {
        i=r;
        ++r;
        while(PQ[i] <= elem && i >= 0) /* Find location for new elem */
        {
            PQ[i+1]=PQ[i];
            i--;
        }
        PQ[i+1]=elem;
    }
}

int PQdelete()
{                      /* Function for Delete operation */
    int elem;
    if(Qempty()){ printf("\n\nUnderflow!!!!\n\n");
    return(-1); }
    else
    {
        elem=PQ[f];
        f=f+1;
        return(elem);
    }
}

int Qfull()
{                     /* Function to Check Queue Full */
    if(r==SIZE-1) return 1;
    return 0;
}

int Qempty()
{                    /* Function to Check Queue Empty */
    if(f > r) return 1;
    return 0;
}

display()
{                  /* Function to display status of Queue */
    int i;
    if(Qempty()) printf(" \n Empty Queue\n");
    else
    {
        printf("Front->");
        for(i=f;i<=r;i++)
            printf("%d ",PQ[i]);
        printf("<-rear font="font">
    }
}

main()
{                         /* Main Program */
    int opn,elem;
    do
    {
        clrscr();
        printf("\n ### Priority Queue Operations(DSC order) ### \n\n");
        printf("\n Press 1-Insert, 2-Delete,3-Display,4-Exit\n");
        printf("\n Your option ? ");
        scanf("%d",&opn);
        switch(opn)
        {
        case 1: printf("\n\nRead the element to be Inserted ?");
            scanf("%d",&elem);
            PQinsert(elem); break;
        case 2: elem=PQdelete();
            if( elem != -1)
                printf("\n\nDeleted Element is %d \n",elem);
            break;
        case 3: printf("\n\nStatus of Queue\n\n");
            display(); break;
        case 4: printf("\n\n Terminating \n\n"); break;
        default: printf("\n\nInvalid Option !!! Try Again !! \n\n");
            break;
        }
        printf("\n\n\n\n  Press a Key to Continue . . . ");
        getch();
    }while(opn != 4);
}

LAST DIGIT 2 SPOJ

5699. The last digit re-visited

Problem code: LASTDIG2




#include<stdio.h>
#include<string.h>
int main()
{
char str[1005];
unsigned long long int b,a,ans,len,t;
scanf("%llu",&t); 
while(t--){
scanf("%s",str);
scanf("%llu",&b);
 len=strlen(str);
//printf("%s\n",str); 
a=str[len-1]-'0'; 
if(b==0&&a!=0) ans=1; 
else{
if(a==0){ ans=0; goto end;}
if(a==5) {ans=5; goto end;}
switch(b%4){
case 0: ans=a%2!=0? 1:6;
break;
case 1: ans=a;
break;
case 2: ans=a*a%10;
break;
default : ans=a*a*a%10;
break; 
}
}
end :
printf("%llu\n",ans);
}
return 0;
}

LAST DIGIT SPOJ

3442. The last digit

Problem code: LASTDIG


Input:
2
3 10
6 2
Output:
9
6
#include<stdio.h>
int main()
{
    int t,a,b,m=10,i=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&a);
        scanf("%d",&b);
        int result=1;
        while(b>0)
        {
            if(b%2==1){
                result=(result*a)%m;
            }
            b=b>>1;
            a=(a*a)%m;
        }
        printf("%d\n",result);
    }
    return 0;
}

FIND NUMBER OF COMMON DIVISOR

Q.) FIND THE NUMBER OF COOMON DIVISOR OF TWO NUMBERS A AND B.
0<=A,B<=10^6



7718. Number of common divisors

Problem code: COMDIV




Input:
3
100000 100000
12 24
747794 238336



Output:

36
6
2

SOLUTION--

#include<stdio.h>

#include<math.h>

int gcd(int a,int b)

{

    if(b==0)

        return a;

    else

        gcd(b,a%b);

}

int main()

{

int t,a,b,num,sqt,i,ans;

scanf("%d",&t);

while(t--)

{

ans=0;

scanf("%d %d",&a,&b);

num=gcd(a,b);

sqt=sqrt(num);

for(i=1;i<=sqt;i++)

{

if(num%i==0){

ans+=2;

if(i==num/i)

ans--;

}

}

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

}

return 0;

}

GENERIC LINK LIST

Q.) IMPLEMENTATION OF GENERIC LINK LIST.

SOLUTION--


#include <stdio.h>

#include <stdlib.h>

#include <string.h>



typedef struct list {

    void *data;

    struct list *next;

} List;
void insert(List **, void *, unsigned int);

void print(List *, void (*)(void *));

void printstr(void *);

void printint(void *);

void printchar(void *);

void printcomp(void *);

List *list1, *list2, *list3, *list4;



int main(void)

{

    char c[]    = { 'a', 'b', 'c', 'd' };

    int i[]     = { 1, 2, 3, 4 };

    char *str[] = { "hello1", "hello2", "hello3", "hello4" };



    list1 = list2 = list3 = list4 = NULL;



    insert(&list1, &c[0], sizeof(char));

    insert(&list1, &c[1], sizeof(char));

    insert(&list1, &c[2], sizeof(char));

    insert(&list1, &c[3], sizeof(char));



    insert(&list2, &i[0], sizeof(int));

    insert(&list2, &i[1], sizeof(int));

    insert(&list2, &i[2], sizeof(int));

    insert(&list2, &i[3], sizeof(int));

    insert(&list3, str[0], strlen(str[0])+1);

    insert(&list3, str[1], strlen(str[0])+1);

    insert(&list3, str[2], strlen(str[0])+1);

    insert(&list3, str[3], strlen(str[0])+1);

    printf("Printing characters:");

    print(list1, printchar);

    printf(" : done\n\n");



    printf("Printing integers:");

    print(list2, printint);

    printf(" : done\n\n");



    printf("Printing strings:");

    print(list3, printstr);

    printf(" : done\n\n");
    return 0;

}

void insert(List **p, void *data, unsigned int n)

{

    List *temp;

    int i;



    /* Error check is ignored */

    temp = malloc(sizeof(List));

    temp->data = malloc(n);

    for (i = 0; i < n; i++)

        *(char *)(temp->data + i) = *(char *)(data + i);

    temp->next = *p;

    *p = temp;

}



void print(List *p, void (*f)(void *))

{

    while (p)

    {

        (*f)(p->data);

        p = p->next;

    }

}



void printstr(void *str)

{

    printf(" \"%s\"", (char *)str);

}



void printint(void *n)

{

    printf(" %d", *(int *)n);

}

void printchar(void *c)

{

    printf(" %c", *(char *)c);

}

INTERSECTION NODES OF LINK LIST

Q.) GIVEN TWO SORTED LINK LIST ,FIND THE INTERSECTION NODES OF THE TWO LINK LIST.

example--
list1={2,4,6,7,8}
list2=(1,2,7,10}

output =2,7

SOLUTION--

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
}*head;
int main()
{
    struct node *head1,*head2,*temp1,*temp2;
    int num1,num2,i,item;
    head1=NULL;
    head2=NULL;
    printf("\nenter the no. nodes in first list=");
    scanf("%d",&num1);
    printf("\nenter the elemnts of node one by one\n");
    for(i=0;i<num1;i++)
    {
        scanf("%d",&item);
        if(head1==NULL)
        {
            head1=malloc(sizeof(struct node));
            head1->data=item;
            temp1=head1;
        }
        else
        {
            temp1->next=malloc(sizeof(struct node));
            temp1->next->data=item;
            temp1=temp1->next;
        }
      //  printf("%d ",temp1->data);
    }
    temp1->next=NULL;
    printf("\nenter the no. of nodes in second list=");
    scanf("%d",&num2);
    printf("\nenter the elements of node one by one\n");
    for(i=0;i<num2;i++)
    {
        scanf("%d",&item);
        if(head2==NULL)
        {
            head2=malloc(sizeof(struct node));
            head2->data=item;
            temp2=head2;
        }
        else
        {
            temp2->next=malloc(sizeof(struct node));
            temp2->next->data=item;
            temp2=temp2->next;
        }
    //    printf("%d ",temp2->data);
    }
    temp2->next=NULL;
    temp1=head1;
    temp2=head2;
    printf("\n intersecting elements of nodes of two given link   
    list\n");
    while(temp1!=NULL&&temp2!=NULL)
    {
        if(temp1->data==temp2->data)
        {
            printf("%d ",temp1->data);
            temp1=temp1->next;
            temp2=temp2->next;
        }
        else if(temp1->data<temp2->data)
            temp1=temp1->next;
        else
            temp2=temp2->next;
    }
    return 0;
}

TIC-TAC-TOE GAME (CODE IN C)

#include <stdio.h>
#include <stdlib.h>

char matrix[3][3];  /* the tic tac toe matrix */

char check(void);
void init_matrix(void);
void get_player_move(void);
void get_computer_move(void);
void disp_matrix(void);

int main(void)
{
  char done;

  printf("This is the game of Tic Tac Toe.\n");
  printf("You will be playing against the computer.\n");

  done =  ' ';
  init_matrix();

  do {
    disp_matrix();
    get_player_move();
    done = check(); /* see if winner */
    if(done!= ' ') break; /* winner!*/
    get_computer_move();
    done = check(); /* see if winner */
  } while(done== ' ');

  if(done=='X') printf("You won!\n");
  else printf("I won!!!!\n");
  disp_matrix(); /* show final positions */

  return 0;
}

/* Initialize the matrix. */
void init_matrix(void)
{
  int i, j;

  for(i=0; i<3; i++)
    for(j=0; j<3; j++) matrix[i][j] =  ' ';
}

/* Get a player's move. */
void get_player_move(void)
{
  int x, y;

  printf("Enter X,Y coordinates for your move: ");
  scanf("%d%*c%d", &x, &y);

  x--; y--;

  if(matrix[x][y]!= ' '){
    printf("Invalid move, try again.\n");
    get_player_move();
  }
  else matrix[x][y] = 'X';
}

/* Get a move from the computer. */
void get_computer_move(void)
{
  int i, j;
  for(i=0; i<3; i++){
    for(j=0; j<3; j++)
      if(matrix[i][j]==' ') break;
    if(matrix[i][j]==' ') break;
  }

  if(i*j==9)  {
    printf("draw\n");
    exit(0);
  }
  else
    matrix[i][j] = 'O';
}

/* Display the matrix on the screen. */
void disp_matrix(void)
{
  int t;

  for(t=0; t<3; t++) {
    printf(" %c | %c | %c ",matrix[t][0],
            matrix[t][1], matrix [t][2]);
    if(t!=2) printf("\n---|---|---\n");
  }
  printf("\n");
}

/* See if there is a winner. */
char check(void)
{
  int i;

  for(i=0; i<3; i++)  /* check rows */
    if(matrix[i][0]==matrix[i][1] &&
       matrix[i][0]==matrix[i][2]) return matrix[i][0];

  for(i=0; i<3; i++)  /* check columns */
    if(matrix[0][i]==matrix[1][i] &&
       matrix[0][i]==matrix[2][i]) return matrix[0][i];

  /* test diagonals */
  if(matrix[0][0]==matrix[1][1] &&
     matrix[1][1]==matrix[2][2])
       return matrix[0][0];

  if(matrix[0][2]==matrix[1][1] &&
     matrix[1][1]==matrix[2][0])
       return matrix[0][2];

  return ' ';
}

SWAP THE K-TH NODE

Written exam (Amazon, Bangalore)

Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.

Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8


SOLUTION USING DOUBLY LINK LIST


#include<stdio.h>
#include<stdlib.h>
int main()
{
    struct node
    {
        int data;
        struct node *next;
        struct node *prev;
    }*head;
    int num,i,k,c,n;
    struct node *temp,*temp1,*temp2,*temp3,*end;
    printf("enter number of link list");
    scanf("%d",&num);
    scanf("%d",&k);
    head=NULL;
    for(i=1;i<=num;i++)
    {
        scanf("%d",&n);
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=n;
            temp=head;
            temp->prev=NULL;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->prev=temp;
            temp->next->data=n;
            temp=temp->next;
        }
    }
    temp->next=NULL;
    end=temp;
    temp1=end;
    temp=head;
    for(i=1;i<=num;i++)
    {
        if(i==k)
        {
            int c=temp->data;
            temp->data=temp1->data;
            temp1->data=c;
        }
        else
        {
            temp=temp->next;
            temp1=temp1->prev;
        }
    }
    temp=head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    return 0;
}

SOLUTION USING SINGLE LINK LIST


#include<stdio.h>
#include<stdlib.h>
int main()
{
    struct node
    {
        int data;
        struct node *next;
    }*head;
    head=NULL;
    int i,num,k,n;
    struct node *temp,*temp1,*temp2;
    printf("enter the number=");
    scanf("%d",&num);
    scanf("%d",&k);
    for(i=1;i<=num;i++)
    {
        scanf("%d",&n);
        if(head==NULL)
        {
            head=malloc(sizeof(struct node));
            head->data=n;
            temp=head;
        }
        else
        {
            temp->next=malloc(sizeof(struct node));
            temp->next->data=n;
            temp=temp->next;
        }
    }
    temp->next=NULL;
    temp=head;
    i=1;
    while(temp!=NULL)
    {
        if(i==k)
        {
            temp1=temp;
            temp=temp->next;
        }
        else if(i==num-k-1)
        {
            temp2=temp;
            temp=temp->next;
        }
        else
        {
            temp=temp->next;
        }
        i=i+1;
    }
    temp=temp1;
    int c=temp->data;
    temp=temp2;
    int d=temp->data;
    temp=temp1;
    temp->data=d;
    temp=temp2;
    temp->data=c;
    temp=head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    return 0;
}