Programs on arrays

Program to print the Matrix in spiral order

#include<stdio.h>
main()
{
int a[10][10],i,j,k,l,m,n,top,bot,lef,rig;
printf("enter the no of rows in the matrix\n");
scanf("%d",&m);
printf("enter the no of columns in the matrix\n");
scanf("%d",&n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
printf("\n");
top=0;
bot=m-1;
lef=0;
rig=n-1;
for(j=0;j<n/2||j<m/2;j++)
{
for(i=lef;i<=rig;i++)
printf("%d ",a[top][i]);
top++;
printf("\n");
for(i=top;i<=bot;i++)
printf("%d ",a[i][rig]);
rig--;
printf("\n");
for(i=rig;i>=lef;i--)
printf("%d ",a[bot][i]);
bot--;
printf("\n");
for(i=bot;i>=top;i--)
printf("%d ",a[i][lef]);
lef++;
printf("\n");
}
}
 TC = Θ(m*n)
   SC = O(1)

Swapping two numbers without using temporary variable

void swap(int *i,int *j)
*i=(*i)^(*j);
*j=(*i)^(*j);
*i=(*i)^(*j);
}

or

void swap(int *i,int *j)

{

*i+=*j;

*j=(*i)-(*j);

*i=(*i)-(*j);

}

Binary search

int binary(int a[],int n,int ele)

{

int m,r=n-1,l=0;

while(l<=r)

{

m=(l+r)/2;

if(a[m]==ele) return m;

else if(a[m]>ele) r=m-1;

else l=m+1;

}

return -1;

}

TC = O(log n)
SC = O(1) 

Given a sorted array which may contain repeated elements, find the left most index of the given number (return -1 if element doesn't exist)

int leftmost(int array[],int n,int ele)

{

int middle,left=0,right=n-1;

while(left<right)

{

middle=(left+right)/2;

if(a[middle]==ele) right=middle;

else if(a[middle]<ele) left=middle+1;

else right=middle-1;

}

if(a[left]==ele)

return left;

else return -1;

}

TC = Θ(log n)
SC = O(1)

An array of size contains all values from 1 to n-1 but one element is repeated. Find the repeated element

int duplicate(int a[],int n)
{
int i,j,res;
for(i=0;i<n;i++)
{
if(a[abs(a[i])]>0)
a[abs(a[i])]*=-1;
else
return abs(a[i]);

}

TC = O(n)
SC = O(1)

An array of size n contains all the elements from 0 to n except one element. Find the missing element

int find_missing(int a[],int n)

{

int i,res=0;

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

{

res=res^a[i];

res=res^(i+1);

}

return res;

}

TC = Θ(n)
SC = O(1)

Check whether the number is palindrome or not

int pal(int n)

{

int i=0;

while(i<n)

{

i*=10;

i+=n%10;

n/=10;

}

if(i==n || n==(i/10))

return 1;

return 0;

}

TC = Θ(log n)
SC = O(1)

Sorting an array with only two values 0 & 1

void sorting(int a[], int n)

{

}

program to print all the prime numbers upto the given number

void primeUptoN(int n)

{

int i=0;

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

if(prime(i))

printf("%d\t",i);

printf("\n");

}

int  prime(int i)

{

int j;

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

if(i%j==0)

return 0;

return 1;

}

Tower of Hanoi

void towerhanoi(char x,char y,char z,int n)

{

if(n==1)

printf("move disk from tower %c to %c\n",x,z);

else

{

towerhanoi(x,z,y,n-1);

printf("move disk from tower %c to %c\n",x,z);

towerhanoi(y,x,z,n-1);

}

}