Rat in a maze - Backtracking method

#include<stdio.h>
#define ROW 4
#define COL 4

int findpath(int maze[ROW][COL],int path[ROW][COL],int i,int j){
static int found = 0;
if(i==ROW-1 && j==COL-1){
path[i][j] = 1;
found = 1;
return 1;
} else {
if(i<ROW && j<COL &&!found && (maze[i][j] == 1)){
path[i][j] = 1;
if(!findpath(maze,path,i+1,j) && !findpath(maze,path,i,j+1)){
path[i][j] = 0;
}
} else {
return 0;
}
}
}

int main(){
int maze[ROW][COL] = {{1,0,0,0},
                              {1,1,0,1},
                              {0,1,1,1},
                              {1,1,0,1}};
int path[ROW][COL] = {{0,0,0,0},
      {0,0,0,0},
      {0,0,0,0},
      {0,0,0,0}};
int i,j;
findpath(maze,path,0,0);
for(i=0;i<ROW;i++){
for(j=0;j<COL;j++){
printf("%d\t",path[i][j]);
}
printf("\n");
}
return 0;
}

First non-repeated character in a string

//INPUT: ramukhsemar
//OUTPUT: first non repeated character = u

#include<stdio.h>

char firstnonrep(char c[]){
int l = strlen(c);
int i;
static int a[256];
for(i=0;i<l;i++){
a[c[i]]++;
}
for(i=0;i<l;i++){
if(a[c[i]] == 1){
return c[i];
}
}
}

int main(){
char c[] = "ramukhsemar";
char p = firstnonrep(c);
printf("first non repeated character = %c",p);
return 0;
}

Find an element in a sorted array which is rotated.

//INPUT : {6,7,8,0,1,2,3,4,5}
//OUTPUT : number found at index 7

#include<stdio.h>

int bsearch(int a[],int low,int high,int n){
if(high-low <=1){
if(a[low] == n) return low;
else if(a[high] == n) return high;
else return -1;
}
int mid = (low+high)/2;
if(a[mid] > a[low]){
if(n>=a[low] && n<=a[mid]){
return bsearch(a,low,mid,n);
} else {
return bsearch(a,mid+1,high,n);
}
} else {
if(n>=a[mid] && n<=a[high]){
return bsearch(a,mid,high,n);
} else {
return bsearch(a,low,mid-1,n);
}
}
}

int main(){
int a[] = {6,7,8,0,1,2,3,4,5};
int i = bsearch(a,0,sizeof(a)/sizeof(a[0])-1,4);
if(i==-1){
printf("number not found!!");
} else {
printf("number found at index %d",i);
}
return 0;
}

Longest Increasing Subsequence

// INPUT = {5,8,0,3,1,9,2,4}
// OUTPUT - Length of LIS = 4 {0,1,2,4} //prints only length
// Complexity - O(n^2)
// If anyone knows about the O(nlogn) solution, feel free to
// mention it in comments section

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

int maxL(int *L,int i,int a[]){
int max = 0;
int j;
for(j=0;j<i;j++){
if(a[j] < a[i] && L[j] > max){
max = L[j];
}
}
return max;
}

int lis(int a[],int n){
int *L = (int *)malloc(sizeof(int)*n);
int i;
int lis = 1;
for(i=0;i<n;i++){
L[i] = maxL(L,i,a)+1;
}
for(i=0;i<n;i++){
if(L[i] > lis){
lis = L[i];
}
}
return lis;
}

int main(){
int a[] = {5,8,0,3,1,9,2,4};
int l = lis(a,sizeof(a)/sizeof(int));
printf("length of LIS = %d",l);
return 0;
}

Reversing words in a String

//INPUT : hello the world
// OUTPUT : world the hello

#include<stdio.h>

void reverse(char *str,int i,int j){
char temp;
while(i<j){
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}

void reverseWords(char *str){
int len = strlen(str);
int start,end;
int i=0;
reverse(str,0,len-1);
while(str[i] != '\0'){
if(str[i] == ' '){
i++;
continue;
} else{
start = i;
while(str[i] != '\0' && str[i] != ' '){
i++;
}
end = i-1;
reverse(str,start,end);
}
}
}

int main(){
char str[] = "hello the world";
reverseWords(str);
printf("%s",str);
return 0;
}

Printing N X N matrix in spiral order

// OUTPUT : 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

#include<stdio.h>
#define MAX 5

void printSpiral(int a[][MAX],int n){
int loop = (n+1)/2;
int i,j,k;
for(k=0;k<loop;k++){
i=k;
j=k;
for(j=k;j<MAX-1-k;j++){
printf("%d ",a[i][j]);
}
for(i=k;i<MAX-1-k;i++){
printf("%d ",a[i][j]);
}
for(j=MAX-1-k;j>k;j--){
printf("%d ",a[i][j]);
}
for(i=MAX-1-k;i>k;i--){
printf("%d ",a[i][j]);
}
}
if(loop%2){
printf("%d",a[loop-1][loop-1]);
}
}

int main(){
        int a[][MAX] = {{1,2,3,4,5},
                      {6,7,8,9,10},
                      {11,12,13,14,15},
                      {16,17,18,19,20},
     {21,22,23,24,25}};
printSpiral(a,MAX);
        return 0;
}

Finding if two numbers are of same sign or opposite sign without using arithmetic operators

#include<stdio.h>

int ifopposite(int a,int b){
return ((a^b) < 0)?1:0;
}

int main(){
int a=-5;
int b=6;
if(ifopposite(a,b)){
printf("numbers are of opposite sign");
} else {
printf("numbers are of same sign");
}
return 0;
}

Longest common prefix of a collection of strings

//INPUT : {"ac","abc","abcd"}
//OUTPUT : a

#include<stdio.h>

#define MAX 10000

char * longestcommonprefix(char *a[],int len){
char out[MAX];
// compare ith and i+1th pointers jth character
int flag = 1;
int i;
int j=0;
while(flag){
for(i=0;i<len-1;i++){
//a[i] points to the ith string
if(*(a[i]+j) == *(a[i+1]+j)){
continue;
} else {
flag = 0;
break;
}
}
if(flag){
out[j] = *(a[i]+j);
if(out[j] == '\0') break;
j++;
}
}
out[j] = '\0';
return out;
}

int main(){
char *a[] = {"ac","abc","abcd"};
char *out = longestcommonprefix(a,sizeof(a)/sizeof(char *));
printf("%s",out);
return 0;
}