Removing Pair in a string.

Suppose we have a string "RGBBGBGR". we have to eliminate the couple (two same chars adjacent to each other) recursively.

For example
RGBBGBGR --> RGGBGR-->RBGR

This solution is O(n) with recursion.

Program code:

#include <stdio.h>

#include <conio.h>

#include <string.h>

void pair_remove(char []);

void main()

{

char a[]="RGBBGBGRRGRR";

clrscr();

pair_remove(a);

printf("%s\n", a);

getch();

}

void pair_remove(char a[])

{

int remove=0,i,j;

int len=strlen(a);

for(i=0;i<len-1;i++){

if( a[i]== a[i+1] )

{

for(j=i+2;j<=len;j++) 

{

a[i]=a[j];

i++;

remove=1;

}

}

if ( remove )

break;

}

if ( remove )

pair_remove(arr);

}

Spiral of a Matrix.

The Following code prints the matrix in a spiral manner.


Program Code:



#include<conio.h>
#include<stdio.h>
void main()
{
int m,n,i,j,left,right,top,down,len,itr;
int a[5][5];
clrscr();
printf ("enter m (max 5):  ");
scanf("%d",&m);
printf ("enter n (max 5):  ");
scanf("%d",&n);
printf ("Enter the elements of matrix one by one\n");
for (i=0;i<m;i++)
    for (j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf ("you have entered the matrix\n");
for (i=0;i<m;i++)
{   for (j=0;j<n;j++)
printf("%6d ",a[i][j]);
    printf ("\n");
}
left=0;
right=n;
top=0;
down=m;
itr=0;
len=m*n;
printf ("\n");
printf ("The spiral form is : ");
printf ("\n");
while (itr<len)
{
for (j=left;j<right;j++,itr++)
printf ("%d ",a[top][j]);
top++;


for (i=top;i<down;i++,itr++)
printf ("%d ",a[i][right-1]);
right--;


for (j=right-1;j>=left;j--,itr++)
printf ("%d ",a[down-1][j]);
down--;


for (i=down-1;i>=top;i--,itr++)
printf ("%d ",a[i][left]);
left++;
}
printf ("\n");
getch();
}

Finding the Odd repeating Number.

Given an array of positive integers. Each number in the array repeats even number of times, only 1 number repeats odd number of times. Find that number.



This Solution is O(n) Time complexity.


#include<stdio.h>
#include<conio.h>
void main()
{
int a[]={4,3,4,3,1};
int len=(sizeof(a)/sizeof(int)),n=a[0],i;
clrscr();
for(i=1;i<len;i++)
{
n^=a[i];
}
printf("%d\n",n);
getch();
}

Inheritance in C.

In C, Inheritance can be implemented through struct.


For example.


struct base
{
/* base class members */
}b;
struct derived
{
struct base super;
/* derived class members */
}d;
void main()
{
struct base *base_ptr = (struct base *)&d; // upcast
getch();
}

Swapping With Pointer.

Swap two pointers without using temporary variables?


#include<stdio.h>
#include<conio.h>
void main()
{
int i=10;
int j=20;
int *a,*b;
clrscr();
a =&i;
b=&j;
printf("Before:%d\t%d\n",*a,*b);
*a^=*b;
*b^=*a;
*a^=*b;
printf("After:%d\t%d\n",*a,*b);
getch();
}

Finiding Max.

Find the maximum of three numbers using conditional operator (ternary operator) ?



#include<stdio.h>
#include<conio.h>
void main()
{
int num1=34,num2=27,num3=61,max;
clrscr();
max=num1 > num2 ? num1 > num3 ? num1: num3: num2 >num3 ? num2: num3;
printf("%d",max);
getch();
}

Problem Based on Array.

Given an array of integers, for each index i, swap the value at i with the first value smaller than a[ i ] that comes after index i. Write a C Program?


For example : If given array is a[]={3,7,4,9,10,2,1}
                        Output         --     a[]={2,4,3,7,9,1,10}


Algorithm:
1) Start from the first element of the array and compare it with rest of the elements.
2) If a element is found which is smaller,swap it and break the execution.
3) Continue with the second element and so on.(until u reach the end of the array)
This solution is O(n^2).
Program:
#include<stdio.h>

#include<conio.h>
void fun(int a[],int,int);void main()
{
int a[]={3,7,4,9,10,2,1};
int len=sizeof(a)/sizeof(int);
int i;
clrscr();
fun(a,0,len);
getch();
}
void fun(int a[],int n,int len)
{
int temp,i;
if(n<len)
{
for(i=n+1;i<len;i++)
if(a[n]>a[i])
{
temp=a[i];
a[i]=a[n];
a[n]=temp;
break;
}
fun(a,n+1,len);
}
else
{
for(i=0;i<len;i++)
printf("%d\t",a[i]);
}
}

Permuting a String.

Write a C program to print all permutations of a given string ?

For Ex: The Permutation of string "ABC" are "ABC, ACB, BAC, BCA, CAB, CBA"

Program: (using backtracking)

# include <stdio.h>

# include <conio.h>

void swap (char *x, char *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

void permute(char *a, int i, int n)

{

   int j;

   if (i == n)

     printf("%s\n", a);

   else

   {

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

       {

 swap((a+i), (a+j));

 permute(a, i+1, n);

 swap((a+i), (a+j)); //backtrack

       }

   }

}

void main()

{

   char a[] = "ABC";

   clrscr();

   permute(a, 0, 2);

   getch();

}

Finding Sub-Strings.

Print all the substrings of a given string.?
Eg: For "abc" the possible substrings are {"a","b","c","ab","bc","abc"}


Algorithm:
1) Start with two nested loops (let the loop variables are i and j, initialize them to 0)
2) Store the sum of the loop variables in another variable(say k) and store the value of (k+1)th element of the string in temporary variable(say tmp).
3) Now set the (k+1)th element of string to 0.(so that it does not print the characters after that element)
4) print the string.(expression as :s+j - so that it starts printing after the j th element in the string).
5) Now store the value of temp into the (k+1)th element of the string.
6) Repeat the steps 2 to 5 till reaching the end of the string(i.e till the termination of first loop).


Program:

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[]="abc";
int i,j;
clrscr();
for( i=0;i <strlen(s);i++)
{
for( j=0;j <strlen(s)-i;j++)
{
int k=j+i;
char tmp=s[k+1];
s[k+1]=0;
printf("%s\n",s+j);
s[k+1]=tmp;
}
}
getch();
}

Finding Repeated Element

Find an integer that repeats more than (>)n/2 times in a given array of size n in O(1) time complexity.? Give an efficient Algorithm?
Note: The array is not sorted.


Algorithm:Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold the required  number.


Program Coding:


#include<stdio.h>
#include<conio.h>


void main()
{
int a[]={5,1,5,2,5,3,5,4,5,3};
int len;
len=sizeof(a)/sizeof(int);
int n,f=1,i;
n=a[0];
clrscr();
for(i=1;i<len;i++)
{
if(f==0)
{
n=a[i];
f=1;
}


if(a[i]==n)
f++;
else
f--;
}
printf("%d",n);
getch();
}