Floor and Ceiling in a sorted array

Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x.

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0:    floor doesn't exist in array,  ceil  = 1
For x = 1:    floor  = 1,  ceil  = 1
For x = 5:    floor  = 2,  ceil  = 8
For x = 20:   floor  = 19,  ceil doesn't exist in array

// Code starts here ,, I used linear search to search the element.

#include<stdio.h>

void fun(int *arr,int arrSize,int *floor,int *ceil,int ele);

int main(void)

{

int arr[] ={1, 2, 8, 10, 10, 12, 19};

int arrSize=sizeof(arr)/sizeof(arr[0]);

int i=0,floor=-1,ceil=10000;

fun(arr,arrSize,&floor,&ceil,9);

if(floor==-1)

{

printf("no floor existsss...");

printf("ceil at indeX==%d\n",ceil);

}

else if(ceil==10000)

{

printf("floor at indeX==%d\n",floor);

printf("no ceil existsss...");

}

else

{

printf("floor at indeX==%d\n",floor);

printf("ceil at indeX==%d\n",ceil);

}

return 0;

}

void fun(int *arr,int arrSize,int *floor,int *ceil,int ele)

{

int i=0,flag=0;

while(i<arrSize)

{

if(ele==arr[i])

{

*floor=i;

*ceil=i;

flag=1;

}

else if(ele>arr[i])

{

*floor=i;

}

else

{

*ceil=i;

flag=1;

}

if(flag==1)

{

break;

}

i++;

}

}

Merge an array of size n into another array of size m+n

There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.

Input: array with m+n elements (mPlusN[]).
NA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.

Input: array with n elements (N[]).

Output: N[] merged into mPlusN[] (Modified mPlusN[])

#include<stdio.h>
#include<stdlib.h>
#define NA 10000 // say the biggest value exist.

// code for maintainind linked list.
// I have to perform insertion operation at end of the list.
// all the time I do not want to traverse the list till end to insert the element , so that I will maintain the last pointer called tail.
// head pointer pointind to the head of the list.
//the insertion operation will return the tail pointer , or pointer to the last inserted node , because when I insert the new element I do not want to traverse the entire list.
// In insert operation I need data to be inserted and pointer to the last node of the list.

struct node
{
int data;
struct node *link;
};

struct node * createNode(int data) // will return the pointer to the newely created node.
{
struct node *p=(struct node *)malloc(sizeof(struct node));
p->link=NULL;
p->data=data;

return p;

}

struct node *insert(struct node *p,int data)
{
struct node * temp=NULL;
temp=createNode(data);

if(p==NULL)// means my list is empty
{
return temp;
}
else
{
p->link=temp;
return temp;
}


}


// I will follow the same process as the mergeSort does.
// But in mergeSort I have to add both the list to the new list.
// Here I have to add the array to the given list.

int main(void)
{

int a[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};
  int b[] = {5, 7, 9, 25};
int arrSizeA=sizeof(a)/sizeof(a[0]);
int arrSizeB=sizeof(b)/sizeof(b[0]);

int i=0,j=0;
struct node *head=NULL,*tail=NULL,*temp=NULL;

while(j<arrSizeB) // while entire B array is scanned...
{

if(head!=NULL)
{
if((head->data) < b[j])
{
a[i]=head->data;
temp=head;
head=head->link;
free(temp);
i++;

if(head==NULL) // to see the list is empty or not , and if empty make teil NULL
{
tail=NULL;
}

}
}// end of outer if


if(b[j] < a[i])
{
if(a[i]==NA) // means there is no element in array a at ith location
{
if(a[i+1]<b[j]) // control jump into this outer if loop , when b[j]<a[i] , but for NA which is the bigger value this condition will always be true.
{
a[i]=a[i+1];
a[i+1]=NA;
i++;
}
else
{
a[i]=b[j];
i++;
j++;
}

}
else // I need to remove the element @ ith location in array a.
{
if(tail==NULL)
{
tail=insert(tail,a[i]);
head=tail; // update head if the element we are going to add is first element in the list.
}
else
{
tail=insert(tail,a[i]);
}

a[i]=b[j];
i++;
j++;


}

}// end of outer if

else // element in a is @ its right place.
{
i++;
}


}// end of while


// print the array.

printf("\ni==%d",i);
printf("\ni==%d \n",j);

for(i=0;i<arrSizeA;i++)
{
printf("-%d-",a[i]);
}



printf("\n");
return 0;
}


// all comments are invited
// please comment if the code do not work for some example.

Search an element in a sorted and pivoted array

An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

// search in two arrays symeltaneously , given that you have pivot element index.
// in the below code pivotPoint is the index of pivot element. // find it your own way.
// searchEle is the element to be searched.
// a is pointer to array.
// arrSize is size of array

int binSearchInRotatedArray(int *a,int arrSize,int pivotPoint,int searchEle)
{

int low1=0,low2=0,high1=0,high2=0,mid1=0,mid2=0;

high1=pivotPoint;
low2=pivotPoint+1;
high2=arrSize-1;

while(1)
{


if(low1>high1)
{
// do nothing..
}
else
{
mid1=(low1+high1)/2;


if(a[mid1]==searchEle)
{
return mid1;
}




else if(a[mid1]>searchEle)
{
high1=mid1-1;

}
else
{
low1=mid1+1;
}

}


if(low2>high2)
{
// do nothing..
}
else
{
mid2=(low2+high2)/2;


if(a[mid2]==searchEle)
{
return mid2;
}



else if(a[mid2]>searchEle)
{
high2=mid2-1;
}
else
{
low2=mid2+1;
}

}

if((low1>high1) && (low2>high2))  // because I have continue the process untill both sides of the array is completly scanned.
{
return -1;

}

}// end of while



}






int main(int argc,char *argv[])
{

int a[]={15,16,19,20,25,1,3,4,5,7,10,14};

int sum=0,i=0,j=0;

int arrSize=sizeof(a)/sizeof(a[0]);


for(j=0;j<arrSize;j++)
{
i=binSearchInRotatedArray(a,arrSize,4,a[j]);

printf("\nyour element %d is at index %d\n",a[j],i);

}
return 0;

}


// time complexity is O(logn) given that you know the index of pivot element.
// so if you find the pivot element it will take O(n) time.
// so total worst case complexity will be n + logn = O(n). // bad idea....

//lets improve this algorithm .

// Here I designed a code which will work even if we do not know the pivot point.
// the worst case time complexity id O(log n).

#include<stdio.h>

int binSearchInRotatedArray(int *a,int arrSize,int searchEle)
{

int low=0,high=(arrSize-1),mid=0;



        while(1)
{
mid=(low+high)/2;



if(a[mid]==searchEle)
{
return mid;
}

else if(a[mid]<searchEle)
{
if(a[high]==searchEle)
{
return high;
}
else  if(a[high]<searchEle)
{
high=mid-1;
}
else
{
low=mid+1;
}

}
else
{
if(a[low]==searchEle)
{
return low;

}
else  if(a[low]<searchEle)
{
high=mid-1;
}
else
{
low=mid+1;
}

}

if(low>=high)
{
return -1;
}

}// end of while


}



int main(int argc,char *argv[])
{

int a[]={15,16,19,20,25,1,3,4,5,7,10,14};

int sum=0,i=0,j=0;

int arrSize=sizeof(a)/sizeof(a[0]);


for(j=0;j<arrSize;j++)
{
i=binSearchInRotatedArray(a,arrSize,a[j]);

printf("\nyour element %d is at index %d\n",a[j],i);

}
return 0;

}

// all the Comments are invited.
// It will be very helpful if you can find the error , please comment below.

Remove Duplicates From Sorted Linked List

Write a removeDuplicatesFromSortedLL() function which takes a list sorted in non-decreasing order and deletes any duplicate nodes from the list. The list should only be traversed once.

For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicatesFromSortedLL() should convert the list to 11->21->43->60.

call the function with head of the linked list.

void removeDuplicatesFromSortedLL(struct node *p1)

{

struct node *p2,*temp=NULL;

int data=-1;

data=p1->data;

p2=p1->link;

while(p2)

{

if((p2->data)==data)

{

temp=p2;

p2=p2->link;

p1->link=p2;

free(temp);

temp=NULL;

}

else

{

data=p2->data;

p1=p1->link;

p2=p2->link;

}

}

}

reverse the DLL iteratively and recursively.

Write a C function to reverse a given Doubly Linked List

See below diagrams for example.

     (a) Original Doubly Linked List  

     (b) Reversed Doubly Linked List  

//Assume that the head and tail pointers are made global , and so is available to the function.

// Iteratively...

void reverseListIteratively()

{

struct node *temp,*p=NULL;

p=head;

while(1)

{

temp=p->left;

p->left=p->right;

p->right=temp;

if((p->right)==NULL)

{

tail=p;

}

if((p->left)==NULL)

{

head=p;

}

p=p->left;

if(p==NULL)

{

break;

}

}

}

// recursively....

void reverseListRecursively(struct node *p)
{
struct node *temp=NULL;

if(p==NULL)
return;

temp=p->left;
p->left=p->right;
p->right=temp;

if((p->right)==NULL)
{
tail=p;
}
if((p->left)==NULL)
{
head=p;
}

reverseListRecursively(p->left);


}

Split a Circular Linked List into two halves

                         Original Linked List  

                         Result Linked List 1  

                         Result Linked List 2  

// create a function which return a pointer to the middle of the node , then arrange the link between the node of the list to make both the list circular.


// here I do not follow that approach , for fun only
// I take two pointer to the pointer.
// say p1 is slow pointer , p2 is fast pointer.
// when p2==head or p2->link->link==head  , p1 is my middle node.
// rather than return the middle pointer , I update the head1 and head2 pointers to head and (mid+1) by using pass by reference.

// so here there is no need to use pass by reference , since we need only one pointer and that is mid pointer that is pointing to the (middle of the list+1)node , and we can have it by returning that pinter(mid+1) form the function.

// time complexity O(n).   :)

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


struct node
{
int data;
struct node *link;

};

struct node *createNode(int data)
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->data=data;
p->link=NULL;

return p;
}

struct node * traverseTillEnd(struct node *head)  // return the last node pointer to the list
{
struct node *p1,*p2=NULL;

if(head==NULL) // return NULL if there is no element in the list
{
return NULL;
}
else if((head->link)==NULL)
{
return head;
}
else
{
p1=head;
p2=p1->link;

while(p2!=head)
{
p1=p1->link;
p2=p2->link;
}

return p1;
}


}


struct node * insertAtEnd(struct node *head,int data)
{

struct node *p=createNode(data);
struct node *temp=NULL;

// traverse till the end of the list. since it is the circular singly linked list, the traversal of ll is litle different.
if(head==NULL)
{
p->link=p;
return p;
}
else
{
temp=(traverseTillEnd(head));
p->link=temp->link;
(temp->link)=p;
}

return head;

}

void printList(struct node *head)
{
struct node *p1=NULL;


if(head==NULL)
{
printf("no element in the list");
}
else
{
p1=head;
printf("-%d-",(p1->data));
p1=p1->link;
while(p1!=head)
{
printf("-%d-",(p1->data));
p1=p1->link;
}
printf("\n");

}

}

void breakListInTwoHalves(struct node *head,struct node **p11,struct node **p22)
{
struct node *p1,*p2,*temp=NULL;
// find the length of the list.
p1=head; // slow pointer
p2=p1->link; // fast pointer

while(p2!=head && (p2->link)!=head)
{
temp=p2;
p1=p1->link;
p2=(p2->link)->link;
//printf("iteration");
}


// setting the values of head1 and head2 of the main

*p22=(p1->link);
*p11=head;



// breaking the list in to two seperate list , so setting the last node link.
if(p2==head)
{
p2=temp->link;  // to point the p2 pointer to the node which is at the end of the list.
}

p2->link=p1->link;
p1->link=head;




}

int main(void)
{

struct node *head=NULL;
head=insertAtEnd(head,5);
head=insertAtEnd(head,3);
head=insertAtEnd(head,6);
head=insertAtEnd(head,1);
head=insertAtEnd(head,7);
head=insertAtEnd(head,10);
head=insertAtEnd(head,15);
//head=insertAtEnd(head,16);
printList(head);

// break the list in two halves ....


struct node *head1,*head2;
breakListInTwoHalves(head,&head1,&head2);


printList(head1);
printList(head2);

//printList(head);

return 0;
}

circular singly linked list

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


struct node
{
int data;
struct node *link;

};

struct node *createNode(int data)
{
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->data=data;
p->link=NULL;

return p;
}

struct node * traverseTillEnd(struct node *head)  // return the last node pointer to the list
{
struct node *p1,*p2=NULL;

if(head==NULL) // return NULL if there is no element in the list
{
return NULL;
}
else if((head->link)==NULL)
{
return head;
}
else
{
p1=head;
p2=p1->link;

while(p2!=head)
{
p1=p1->link;
p2=p2->link;
}

return p1;
}


}


struct node * insertAtEnd(struct node *head,int data)
{

struct node *p=createNode(data);
struct node *temp=NULL;

// traverse till the end of the list. since it is the circular singly linked list, the traversal of ll is litle different.
if(head==NULL)
{
p->link=p;
return p;
}
else
{
temp=(traverseTillEnd(head));
p->link=temp->link;
(temp->link)=p;
}

return head;

}

void printList(struct node *head)
{
struct node *p1=NULL;


if(head==NULL)
{
printf("no element in the list");
}
else
{
p1=head;
printf("-%d-",(p1->data));
p1=p1->link;
while(p1!=head)
{
printf("-%d-",(p1->data));
p1=p1->link;
}
printf("\n");

}

}


int main(void)
{

struct node *head=NULL;
head=insertAtEnd(head,5);
head=insertAtEnd(head,3);
head=insertAtEnd(head,6);
head=insertAtEnd(head,1);
head=insertAtEnd(head,7);


printList(head);

return 0;
}

Write a function to reverse a linked list

struct node * reverseSLL2(struct node *p,struct node *temp)
{
struct node *temp1;
if(p!=NULL)
{
temp1=p->link;
p->link=temp;
return reverseSLL2(temp1,p);
}
else
{
return temp;
}


}

call head=reverseSLL2(head,NULL);

where head is a pointer pointing to first node in the list.

Pairwise swap elements of a given linked list

Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.



// I have two functions hear insertAtEnd()  and insertAtBegin() for sake of fun only. you can create the linked list your own  way. Just concentrate on pairWiseSwapOfGivenLL() function for the sollution.


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

struct node
{
int data;
struct node *link;
};


struct node * insertAtEnd(struct node *head,int data)
{
if(head==NULL)
{
struct node *n1;
n1=(struct node *)malloc(sizeof(struct node));
n1->data=data;
n1->link=NULL;

head=n1;


}
else
{
struct node *n1;
n1=(struct node *)malloc(sizeof(struct node));
n1->data=data;
n1->link=NULL;

// traverse to the end of the list.

struct node *temp;
temp=head;
while((temp->link)!=NULL)
{
temp=temp->link;
}

temp->link=n1;
}

return head;
}


struct node * insertAtBegin(struct node *head,int data)
{
struct node *n1;
n1=(struct node *)malloc(sizeof(struct node));
n1->data=data;

if(head==NULL)
{
n1->link=NULL;
}
else
{
n1->link=head;
}

head=n1;

return head;
}

void printList(struct node *head)
{
if(head==NULL)
{
printf("no element in list");
}
else
{
struct node *temp;
temp=head;
while(temp!=NULL)
{
printf("--%d--",(temp->data));
temp=temp->link;
}

printf("\n\n");
}


}


struct node * pairWiseSwapOfGivenLL(struct node *head)
{
struct node *p1,*p2,*temp=NULL;

p1=head;
p2=p1->link;

while(p2)
{
if(p1==head)
{
p1->link=p2->link;
p2->link=p1;
head=p2;
temp=p1;
p1=p1->link;
p2=p1->link;
}
else
{
p1->link=p2->link;
p2->link=p1;
temp->link=p2;
temp=p1;
p1=p1->link;
if(p1==NULL)
{
break;
}
else
{
p2=p1->link;
}
}
}

return head;

}

int main(void)
{

struct node *head=NULL;
struct node *p,*temp=NULL;

head=insertAtEnd(head,7);
head=insertAtEnd(head,8);
head=insertAtBegin(head,6);
head=insertAtBegin(head,5);
head=insertAtEnd(head,9);
head=insertAtEnd(head,10);
//head=insertAtEnd(head,11);
//head=insertAtEnd(head,12);

printList(head);

head=pairWiseSwapOfGivenLL(head);

printList(head);



return 0;
}