Remove adjacent duplicates

Given a string, recursively remove adjacent duplicate characters from string. The output string should not have any adjacent duplicates.


Input:
geeeksforgeek

Output:
gksforgk


Check my geeksforgeeks submission: http://www.practice.geeksforgeeks.org/viewSol.php?subId=1579026&pid=1583

Answer: (Solution using both loops & recursion is present)

#include <stdio.h>
#include <string.h>
void duplicate_removal(char *s)
{
   static char *p, *q;
   static char flag = 0;

   if(flag == 1) {
      if(*p != *s) {
         q = s;
 flag = 2;
 return;
      }
      duplicate_removal(++s);
      s = p;
   }

   if((flag == 2) && (*q == '\0')) {
      *s = '\0';
      flag = 0;
      return;
   }

   if(flag == 2) {
      *s = *q++;
   }

   if(*s == '\0') {
      flag = 0;
      return;
   }
   else if ((flag == 0) && (*s == *(s+1))) {
      p = s;
      flag = 1;
      duplicate_removal(s);
      s = p;
   }

   duplicate_removal(++s);
}


int main(void) {
   char buff[32];
#if 0
   int i,j,k,l,len;
#endif

   printf("String: ");
   scanf("%s",buff);

#if 0
   len = strlen(buff);

   for(i=0; i<len; i++) {
      if(buff[i] == buff[i+1]) {
         for(k=i; k<len; k++) {
            if(buff[i] != buff[k]) {
               j = k;
               break;
            }
         }

         for(k=j,l=i; k<len; k++,l++) {
            buff[l] = buff[k];
         }
         buff[l] = '\0';
      }
      len = strlen(buff);
   }
#endif

   duplicate_removal(buff);
   printf("Output: %s\n",buff);
   return 0;
}

Path traversal

Given a matrix with 0’s and 1’s , you enter the matrix at cell (0,0) in left to right direction. whenever you encounter a 0 you retain in same direction , if you encounter a 1’s you have to change direction to right of current direction and change that 1 value to 0, you have to find out from which index you will leave the matrix at the end.

Input:
3 3
0 0 1 0 0 0 0 0 0

Output:
2 2 

Input:
2 4
0 0 0 1 0 0 1 1

Output:
0 2

Example: The matrix will be represented as
0 1 1 1 0 
1 0 1 0 1 
1 1 1 0 0

The path is 
(0,0) (0,1) (1,1) (2,1) (2,0) (1,0) (1,1) (1,2) (2,2) (2,1) (2,0)


Answer:

Check my geeksforgeeks submission: http://www.practice.geeksforgeeks.org/viewSol.php?subId=1574427&pid=1586

#include <stdio.h>

// RR = Row Right
// CD = Column Down
// RL = Row Left
// CU = Column Up
enum state { RR, CD, RL, CU};

void change_state(int *curstate)
{
if(*curstate == CU)
*curstate = RR;
else 
  *curstate = *curstate + 1;
}

void parse_state(int *curstate, int *i, int *j)
{
printf(" %d,%d\n",*i,*j);
switch(*curstate) {
case RR:
*j = *j + 1;
break;
case CD:
*i = *i + 1;
break;
case RL:
*j = *j - 1;
break;
case CU:
*i = *i - 1;
break;
default:
break;
}
}

void print_exitpath(int r, int c, int (*p)[10][10]) {
int i=0,j=0;
int curstate = RR;

 while((i>=0) && (i<x) && (j>=0) && (j<y)) {
if((*p)[i][j] == 1) {
(*p)[i][j] = 0;
change_state(&curstate);
}
parse_state(&curstate, &i, &j);
}
}

int main(void) {
int r, c,i,j;
int a[10][10];

printf("r: ");
scanf("%d",&r);
printf("c: ");
scanf("%d",&c);
for(i=0; i < r ; i++) {
for(j=0; j
printf("Value[%d][%d]: ",i,j);
scanf("%d",&a[i][j]);
}
}

print_exitpath(r,c,&a);
return 0;
}

Pattern count

Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence.

Example:
Input:
100001abc101
1001ab010abc01001
10101010

Output:
2
2
3

Check my geeksforgeeks submission: http://www.practice.geeksforgeeks.org/viewSol.php?subId=1574505&pid=1598

Answer 1: (Unoptimized)
#include <stdio.h>

int main(void)
{
char buff[32];
int count = 0, i = 0, zflag = 0,oflag = 0;

printf("String: ");
scanf("%s",buff);

while(buff[i] != '\0') {
if(buff[i] == '0') {
if(oflag == 1) {
oflag = 0;
zflag = 1;
}
}
else if(buff[i] == '1') {
oflag = 1;
if(zflag == 1) {
//oflag = 0;
zflag = 0;
count++;
}
}
else {
oflag = 0;
zflag = 0;
}
i++;
}
printf("Count = %d\n",count);

return 0;
}

Answer2: (Better version)
#include <stdio.h>
#include <string.h>

int patterncount(char *s)
{
int len = strlen(s), i, count = 0;

for(i = 0; i < len; i++) {
if(s[i] == '1' && s[i+1] == '0') {
i++;
for(; i < len; i++) {
if(s[i] == '1') {
count++;
i--;
break;
}
else if (s[i] != '0')
break;
}
}
}
return count;
}

int main(void)
{
char buff[32];

printf("String: ");
scanf("%s", buff);

printf("Count = %d\n",patterncount(buff));

return 0;
}