Q. N persons are standing in a circle and play a game which starts from 1. In this game we are passing each other baton and after count of D which ever person holds that baton is out from the game and then the game begins from the next person in the circle. Print the order in which the people gets out.

INPUT  N=5,  D=2;

OUTPUT:  2,4,1,5,3

First  2  gets  out  then  4  so  we  left  with  1  3  5
Game  starts  with  5  and  hence  1  gets  out  and  game  goes  like  that.........



Solution:-  We  are  initializing  an  array  with  size  N  with  a[i]=i;

Now  we  are  counting  (prevIndex+D)%length;  length--;  is  the  next  element  to  be  removed

length  is  updated  dynamically

And  the  element  removed  is  printed...

#include<stdio.h>

void remove(int*,int,int);

void remove(int *arr,int k,int n)
{
for(int i=k+1;i<n;i++)
    arr[i-1]=arr[i];
}


int main()
{
        int n=12;
        int d=2;
        int arr[n];
        int length=n;
        int v=0;
     
        for(int k=0;k<n;k++)
        arr[k]=k+1;  
     
     
        while(1)
        {
                if(length==1)
                break;
         
             if(v!=0)
                v=v+d-1;
                else
                v=v+d;
             
                if(v%length!=0 || v==0)
                v=v%length;
                else
                v=length;
     
     
        printf("%d\n",arr[v-1]);
     
        if(v!=0)
        remove(arr,v-1,length);
        else
        remove(arr,v,length);
     
        length--;
     
        if(v>length)
        v=0;
     
        }
        printf("%d",arr[0]);  
        return 0;
}

If  you  fell  asking  anything  please  tell  me  anytime....

Q. Spiral Traversal of a nxn matrix where n is odd..

Well  this  is  a  really  good  question  for  your  coding  practice. This  is asked  in  many  interviews  to  check  the  coding  abilities  of  the  candidiates

Lets  have  a  5x5  matrix  as  an  example


0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24



for  this  answer  should  be
0 1 2 3 4 9 14 19 24 23 22 21 20 15 10 5 6 7 8 13 18 17 16 11 12

Time  Complexity=O(n)
Space Complexity=O(1)


#include<stdio.h>

int main()
{
int n=5;
int arr[n][n];
int top=0,bottom=n,left=0,right=n;//these  are  the  boundaries  of  the  matrix  while  traversing  spirally
int currX=0,currY=0;//these  are  the  locations  which  are  being  traversed

//arr  is  having  value  0 to 48  in  row  majority  order
for(int k=0;k<n;k++)
for(int k1=0;k1<n;k1++)
arr[k][k1]=n*k+k1;

// this is for printing matrix value
/*for(int k=0;k<n;k++)
{
for(int k1=0;k1<n;k1++)
printf("%d\t",arr[k][k1]);
printf("\n");
}*/


while((currX!=n/2)&&(currY!=n/2))
{
//printf("%d %d %d %d\n",left,right,top,bottom);
while(currX<right)
{printf("%d\t",arr[currY][currX]);currX++;}right--;currX--;currY++;top++;

while(currY<bottom)
{printf("%d\t",arr[currY][currX]);currY++;}bottom--;currY--;currX--;

while(currX>=left)
{printf("%d\t",arr[currY][currX]);currX--;}left++;currX++;currY--;

while(currY>=top)
{printf("%d\t",arr[currY][currX]);currY--;}currY++;currX++;
}
printf("%d",arr[n/2][n/2]);
return 0;
}

Q. Position all elements less than 0 before elements greater than 0

INPUT                     6, -1, -2, 2, -4, 3, 5
OUTPUT                 -4, -2,-1  2 ,6 ,3 ,5

This  is  a  very  common  question  asked  in  which  can  be  of  form  arranging  all  even  numbers  before than  odd  ones  or  keeping  all  0  values  before  1 etc....  And  they  always  expect  you  to  solve  in  one  scan  and  in  place...

METHOD 1

In  this  we  take  another  array  of  same  size  and  first  push  all  the  negative  elements  and  then  in  second  scan  er  push  all  positive  elements..

Time  Complexity= O(n)

Space COmplexity=O(n)

METHOD 2

We  take  two  pointers  ptr1  and  ptr2.

ptr1  points  to  first  occurence  of  positive  elements,,

and  ptr2  searches  the  negative  number  to  the  right  of  ptr1  if  we  do  not  find  any  -ve  number  we  break...

else  we  we  swap  them  and  find  our  new  ptr1  which  is  obviously  greater  than  the  previous  value

#include<stdio.h>
void swap(int*,int,int);
void swap(int *arr,int ptr1,int ptr2)
{
int temp=arr[ptr1];
arr[ptr1]=arr[ptr2];
arr[ptr2]=temp; }

int main()
{
int bbreak=true;
int arr[7]={6, -1, -2, 2, -4, 3, 5};
int ptr1=-1,ptr2=-1;
//ptr1 maintains  the  first  +ve  element
while(1)
{
for(int k=ptr1;k<7;k++)
if(arr[k]>0)
{ptr1=k;break;}
for(int k=ptr1;k<7;k++)
{
if(arr[k]<0)
{swap(arr,ptr1,k);bbreak=false;}
}
if(bbreak==true)
break;
bbreak=true;
}
for(int k=0;k<7;k++)
printf("%d\t",arr[k]);
}