WAP to Remove The Node From Binary Search Tree

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

struct node* search(struct node* tmp, struct node** parent,struct node* item)
{
struct node* root;
root=tmp;

if(!root)
{
//*parent=NULL;
return NULL;
}
if(root->data==item->data)
{
return root;
}

*parent=root;

if(item->data<=root->data)
{
return search(root->left,parent,item);
}
else
{

return search(root->right,parent,item);
}

}

void deletes(struct node* root,struct node* srch)
{
struct node* parent;
struct node* succ=NULL;

if(!root)
return;

parent=NULL;

struct node* x=search(root,&parent,srch);

/* if the node to be deleted has no child */
if(x->left==NULL && x->right==NULL)
{

if(parent->left==x)
parent->left=NULL;
else
parent->right=NULL;

free(x);
return;
}


/* if the node to be deleted has only rightchild */
if (x->left == NULL && x->right!= NULL )
{
if ( parent->left == x )
parent->left = x->right ;
else
parent->right= x->right;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if (x->left != NULL && x->right== NULL )
{
if ( parent->left == x )
parent->left= x->left ;
else
parent->right = x->left ;

free ( x ) ;
return ;
}


/* if the node to be deleted has two children */

if(x->left!=NULL && x->right!=NULL)
{
parent=x;
succ=x->right;

while(succ->left!=NULL)
{
parent=succ;
succ=succ->left;
}

x->data=succ->data;
x=succ;
free(x);//free(succ).....problem Might be here I dont Know why
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}


/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

struct node* parent= NULL;

root=search(root,&parent,root->left->right);
printf(" %d %d ", root->data, parent->data);

deletes(root,root->left->right);

printInorder(root);

getchar();
return 0;
}

Page Replacement Algorithm Using FIFO (Queue)

#include
#include
void main()
{
int a,b,ct=0,co=0,pf=0,list[30],arr[10],i,j,l;
clrscr();
printf("\n enter no fo processors:");
scanf("%d",&a);
printf("\n enter the series:");
for(i=0;i
scanf("%d",&list[i]);
printf("\n enter the no of frames:");
scanf("%d",&b);
for(i=0;i
arr[i]=0;
for(i=0;i
{
co=0;
if(ct==b)
ct=0;
for(int j=0;j
{
if(arr[j]==list[i])


{
co=1;
break;
}
}
if(co==0)
{
arr[ct]=list[i];
pf++;
ct++;
printf("\nf");
}
for(int l=0;l
printf("%d",arr[l]);
printf("\n");
}
printf("\n no of page faults are : %d",pf);
getch();
}



----------------------------------------------------------
OUT PUT:
----------------------------------------------------------
Enter no of processors: 3
Enter the series:
3
5
7
Enter the no of frames: 3
F400
F450
F457
No of page faults are :3

WAP to Implemen The All Function Of Doubly Linked lIst

import java.util.Iterator;




public class DoublyLInkedList {


Node head = null;
Node tail = null;




public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public Node getTail() {
return tail;
}
public void setTail(Node tail) {
this.tail = tail;
}

private Node createNode(T data) {
Node node = new Node();
node.setData(data);
node.setNext(null);
node.setPrevious(null);
return node;

}

public void insertAtHead(Node node) {
if (getHead() == null) {
System.out.println("Creating first Head " + node.getData());
setHead(node);
setTail(node);
}
else {
node.setPrevious(null);
node.setNext(getHead());
getHead().setPrevious(node);
setHead(node);
System.out.println("Inserting at head " + node.getData());
}

}

public Node insertAtHead(T data) {
if (data == null)
return null;
//if head is null first node
Node node = createNode(data);
insertAtHead(node);
return node;
}

private Node findNode(T data) {
Node tmp = head;
while(tmp != null) {
//System.out.println("findNode :: Comparing " + tmp.getData() + " with " + data);
if (tmp.getData().equals(data))
return tmp;
tmp = tmp.getNext();
}
return null;
}

public void remove(T data) {
Node node = findNode(data);
remove(node);
}

public void remove(Node node) {
if (node == null)
return;
//1 node in list
if (node.getPrevious() == null &&
node.getNext() == null) {
setHead(null);
setTail(null);
return;
}
//head node
if (node.getPrevious() == null &&
node.getNext() != null) {
//head node
setHead(node.getNext());
node.setNext(null);
return;
}
// tail node
if (node.getNext() == null &&
node.getPrevious() != null) {
//tail node
setTail(node.getPrevious());
node.getPrevious().setNext(null);
return;
}
// center node
System.out.println("Removing center node from list with value [ " + node.getData() + "] whose previous = [" + node.getPrevious().getData() + "] and next = [" + node.getNext().getData() + "]");
node.getPrevious().setNext(node.getNext());
node.getNext().setPrevious(node.getPrevious());
node.setNext(null); node.setPrevious(null);
}


private class ListIterator implements java.util.Iterator {
Node currentNode;

public ListIterator() {
currentNode = getHead();

}

public boolean hasNext() {
// TODO Auto-generated method stub
if (currentNode != null)
{
// System.out.println("Current node is not null and is pointing to " + currentNode.getData());
return true;
}
else
return false;
}

public T next() {
// TODO Auto-generated method stub
//System.out.println("Current node = " + currentNode.getData() );
T data = (T) currentNode.getData();
currentNode = currentNode.getNext();
return data;
}

public void remove() {
// TODO Auto-generated method stub
DoublyLInkedList.this.remove(currentNode);

}
}

public Iterator iterator() {
return new ListIterator();

}

public static void main(String[] args) {
System.out.println("Test");
DoublyLInkedList dList = new DoublyLInkedList();
String str1 = new String("1");
String str2 = new String("2");
String str3 = new String("3");
dList.insertAtHead(str1);
dList.insertAtHead(str2);
dList.insertAtHead(str3);
Iterator it = dList.iterator();
while (it.hasNext()) {
System.out.println(it.next());

}
System.out.println("Tail Node = " + dList.getTail().getData());
dList.remove(str1);
Iterator it1 = dList.iterator();
while (it1.hasNext()) {
System.out.println(it1.next());

}
System.out.println("Tail Node = " + dList.getTail().getData());

}

}


Sourse https://github.com/inders/datastructure-repo/blob/master/LRUCache/src/DoublyLInkedList.java

WAP Find Minimum In Difference betwen Two Array..Its Different Question,Have A Closer Look

Consider two non-empty zero-indexed arrays A and B consisting of N integers each. Four functions are defined based on these arrays:

F(X,K) = A[K]*X + B[K]
U(X) = max { F(X,K) : 0 <= K < N }
D(X) = min { F(X,K) : 0 <= K < N }
S(X) = U(X) - D(X)

Write a function

double minfuds(int[] A, int[] B);

that given two arrays A and B returns the minimum value of S(X) where X can be any real number. Assume that the arrays have equal length and that it does not exceed 100,000. Assume that each element of the arrays is an integer in range [-1,000..1,000].

For example, given arrays A and B such that

A[0] = -1 B[0] = 3
A[1] = 1 B[1] = 0
A[2] = 0 B[2] = 2

the function should return 0.5 because

U(X) = -1*X + 3 if X <= 1
U(X) = 0*X + 2 if 1 < X <= 2
U(X) = 1*X + 0 if 2 < X

and

D(X) = 1*X + 0 if X <= 1.5
D(X) = -1*X + 3 if 1.5 < X

so for X = 1.5 function S(X) is equal to 0.5 and this is the minimum value of this function.


class array
{
static double minfuds ( double [] a, double [] b )
{
double x=1.5;
double c[]=new double[a.length];
for(int i=0;i {
c[i]=a[i]*x+b[i];
}
double min=1000.0;
double max=-1000.0;
for(int j=0;j {
if(c[j]>max)
max=c[j];

if(c[j] min=c[j];
// write your code here
}

return (max-min);

}


public static void main(String a[])
{

System.out.println(minfuds(new double []{-1, 1, 0},new double []{3, 0, 2}));

}
}

Run Here https://ideone.com/Qo9Kc

Check for balanced parentheses in an expression

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[","]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”


#include
#include
#define bool int

/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else if(character1 == '[' && character2 == ']')
return 1;
else
return 0;
}

/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;

/* Declare an empty character stack */
struct sNode *stack = NULL;

/* Traverse the given expression to check matching parenthesis */
while(exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);

/* If exp[i] is a ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{

/*If we see an ending parenthesis without a pair then return false*/
if(stack == NULL)
return 0;

/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}

/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if(stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}

/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[100] = "{()}[]";
if(areParenthesisBalanced(exp))
printf("\n Balanced ");
else
printf("\n Not Balanced "); \
getchar();
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;

/*If stack is empty then error */
if(*top_ref == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

Source Geeks4Geeks

WAP to Find Longest Comman Subsequence

The longest common subsequence (or LCS) of groups A and B is the longest group of elements from A and B that are common between the two groups and in the same order in each group. For example, the sequences "1234" and "1224533324" have an LCS of "1234":

1234
1224533324

For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest":

thisisatest
testing123testing

In this puzzle, your code only needs to deal with strings. Write a function which returns an LCS of two strings (case-sensitive). You don't need to show multiple LCS's.

More Info Wiki

C Code of LCS

#include
#include
#include

#define MAX(A,B) (((A)>(B))? (A) : (B))

char * lcs(const char *a,const char * b) {
int lena = strlen(a)+1;
int lenb = strlen(b)+1;

int bufrlen = 40;
char bufr[40], *result;

int i,j;
const char *x, *y;
int *la = calloc(lena*lenb, sizeof( int));
int **lengths = malloc( lena*sizeof( int*));
for (i=0; i
for (i=0,x=a; *x; i++, x++) {
for (j=0,y=b; *y; j++,y++ ) {
if (*x == *y) {
lengths[i+1][j+1] = lengths[i][j] +1;
}
else {
int ml = MAX(lengths[i+1][j], lengths[i][j+1]);
lengths[i+1][j+1] = ml;
}
}
}

result = bufr+bufrlen;
*--result = '\0';
i = lena-1; j = lenb-1;
while ( (i>0) && (j>0) ) {
if (lengths[i][j] == lengths[i-1][j]) i -= 1;
else if (lengths[i][j] == lengths[i][j-1]) j-= 1;
else {
// assert( a[i-1] == b[j-1]);
*--result = a[i-1];
i-=1; j-=1;
}
}
free(la); free(lengths);
return strdup(result);
}

int main()
{
printf("%s\n", lcs("thisisatest", "testing123testing")); // tsitest
return 0;
}

Run Here https://ideone.com/tCMa0

Java Code of LCS

class LCS
{

public static String lcs_dp(String a, String b) {
int[][] lengths = new int[a.length()+1][b.length()+1];

// row 0 and column 0 are initialized to 0 already

for (int i = 0; i < a.length(); i++)
for (int j = 0; j < b.length(); j++)
if (a.charAt(i) == b.charAt(j))
lengths[i+1][j+1] = lengths[i][j] + 1;
else
lengths[i+1][j+1] =
Math.max(lengths[i+1][j], lengths[i][j+1]);

// read the substring out from the matrix
StringBuffer sb = new StringBuffer();
for (int x = a.length(), y = b.length();
x != 0 && y != 0; ) {
if (lengths[x][y] == lengths[x-1][y])
x--;
else if (lengths[x][y] == lengths[x][y-1])
y--;
else {
assert a.charAt(x-1) == b.charAt(y-1);
sb.append(a.charAt(x-1));
x--;
y--;
}
}

return sb.reverse().toString();
}


public static String lcs_rec(String a, String b){
int aLen = a.length();
int bLen = b.length();
if(aLen == 0 || bLen == 0){
return "";
}else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
return lcs_rec(a.substring(0,aLen-1),b.substring(0,bLen-1))
+ a.charAt(aLen-1);
}else{
String x = lcs_rec(a, b.substring(0,bLen-1));
String y = lcs_rec(a.substring(0,aLen-1), b);
return (x.length() > y.length()) ? x : y;
}
}

public static void main(String a[])
{
System.out.println(lcs_rec("ABCDEFG", "FACHDGB"));
System.out.println(lcs_dp("ABCDEFG", "FACHDGB"));

}

}

Source http://www.ics.uci.edu/~eppstein/161/960229.html

Run Here https://ideone.com/lsc8b

WAP to Print All Possible Combination of Balanced Parenthesis

# include
# define MAX_SIZE 100

void _printParenthesis(int pos, int n, int open, int close);

/* Wrapper over _printParenthesis()*/
void printParenthesis(int n)
{
if(n > 0)
_printParenthesis(0, n, 0, 0);
return;
}

void _printParenthesis(int pos, int n, int open, int close)
{
static char str[MAX_SIZE];

if(close == n)
{
printf("%s \n", str);
return;
}
else
{
if(open > close) {
str[pos] = '}';
_printParenthesis(pos+1, n, open, close+1);
}
if(open < n) {
str[pos] = '{';
_printParenthesis(pos+1, n, open+1, close);
}
}
}

/* driver program to test above functions */
int main()
{
int n = 3;
printParenthesis(n);
getchar();
return 0;
}

WAP to Find Next Greater Palindrom Then the Given Number

#include

int ten(int s)
{
int i=1,product=1;
for(i=1;i<=s;i++)
product=product*10;
return product;
}
int main()
{
int n=0,num=0,b=0,c=0,d=0,i=1,input=99999,upper=0,lower=0,output=0;

num=input;
while(num!=0)
{
n++;
num/=10;
}
num=input;
printf("\n n=%d",n);
lower=num%ten(n/2);
printf("\nlower=%d",lower); //34 45
c=num/ten(n/2); //12 123
d=c;
if(n%2!=0)//if not even digits
d=c/10; // 12 12
printf("\n%d%d",c,d);
while(d!=0)
{
upper=upper*10+(d%10);
d=d/10;
}
printf("\nupper=%d",upper);//21 21
if(upper>lower)
{
output=c*ten(n/2)+upper;
}
else
{
c=c+1; //124
d=c;
upper=0;
if(n%2!=0)
d=d/10; //12
while(d!=0)
{
upper=upper*10+(d%10);
printf("\nd=%d",d);
d=d/10;
}
output=c*ten(n/2)+upper;
}
printf("\noutput=%d",output); //1331 12421

}

WAP to Removing characters from an input string in place.

#include
#include

WAP To Implement The Bitonic Sorting Can Be extended to K-tonic Sorting

public class BitonicSorterForArbitraryN
{
private static int[] a;
private final static boolean ASCENDING=true; // sorting direction

public static void sort(int[] ar)
{
a=ar;
bitonicSort(0, a.length, ASCENDING);
}

private static void bitonicSort(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, !dir);
bitonicSort(lo+m, n-m, dir);
bitonicMerge(lo, n, dir);
}
}

private static void bitonicMerge(int lo, int n, boolean dir)
{
if (n>1)
{
int m=greatestPowerOfTwoLessThan(n);
for (int i=lo; i compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, n-m, dir);
}
}

private static void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}

private static void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}

private static int greatestPowerOfTwoLessThan(int n)
{
int k=1;
while (k k=k<<1;
return k>>1;
}

public static void main(String ar[])
{
int a[]={1,2,3,4,5,9,8,7,6};
sort(a);
for(int i=0;i<9;i++)
System.out.println(a[i]);
}

}

The new sorting network for arbitrary n can be embedded into an original bitonic sorting network for 2k. Therefore, it also consists of ceiling 1log(n)ceiling 2 · (ceiling 1log(n)ceiling 2 + 1) / 2 stages. Each stage consists of at most n/2 comparators. This results in a complexity of O(n log(n)2) comparators, just as the original bitonic sorting network.


Time Complexity O(n(logn)^2))
Space O(1)

WAP remove(Delete Node From Binary Tree

WAP to SumTwo Number Which are represented by node in linked list

#include<stdio.h>
#include<malloc.h>
 
/* Link list node */
struct node
{
int data;
struct node* next;
};
 
/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
 
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
 
/* put in the data */
new_node->data = new_data;
 
/* link the old list off the new node */
new_node->next = (*head_ref); 
 
/* move the head to point to the new node */
(*head_ref) = new_node;
}
 
 
 
struct node* addition (struct node* temp1, struct node* temp2)
{
 
struct node* prev = NULL;
int carry = 0,a,b,result;
 
while (temp1 || temp2) //while both lists exist
{
 
if(temp1) a=temp1->data;
else a=0;
 
if(temp2) b=temp2->data;
else b=0;
 
 
 
 
result = carry;
if(temp1)
result+=temp1->data;
if(temp2)
result+=temp2->data;
 
 
carry=result/10;
 
struct node * newnode = (struct node*) malloc (sizeof(struct node));
newnode->data=(result)%10;
newnode->next = prev;
 
prev=newnode;
if(temp1)
temp1=temp1->next;
if(temp2)
temp2=temp2->next;
}
return prev;
 
}
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
} 
 
/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;
struct node* head1 = NULL;
struct node* head2 = NULL;
 
 
/* Created Linked list is 1->2->3->4->5->6->7->8 */
 
push(&head1, 4);
push(&head1, 3);
push(&head1, 2);
push(&head1, 1);
 
reverse(&head1); 
 
push(&head2, 6);
push(&head2, 5);
push(&head2, 4);
 
reverse(&head2); 
 
head=addition(head1,head2); 
 
 
 
printList(head);
 
return(0);
}

TC O(n+m) where n,m are the number of digits in given numbers.
SC O(1)
Run Here https://ideone.com/j4Z8Z

WAP Find Minimu Number of Jumps to Reach In The End , In An UnSorted Array

#include
#include

int main()
{

int arr[] = {1 ,3, 5, 8 ,9 ,2, 6,7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int size=11;

int step=0,jump=0;
int i=0,j=0,max=0;

while( i< size)
{
jump++;
max=0;
step=0;

/*computes max distance it can cover in this jump*/
for(j=1;j<=arr[i];j++)
{
if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf ( " %d ",jump);



return 0;
}

Run Here https://ideone.com/bvQph
Still DP is Best Will Post Soln Soon Using DP

WAP Find Minimu Number of Jumps to Reach In The End , In An UnSorted Array

#include
#include

int main()
{

int arr[] = {1 ,3, 5, 8 ,9 ,2, 6,7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int size=11;

int step=0,jump=0;
int i=0,j=0,max=0;

while( i< size)
{
jump++;
max=0;
step=0;

/*computes max distance it can cover in this jump*/
for(j=1;j<=arr[i];j++)
{
if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf ( " %d ",jump);



return 0;
}

WAP to Find & Remove The Loop From Linked List

1st Algorithm:
Floyd’s Cycle-Finding Algorithm:

Algorithm
This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

Working Code For Loop Detection

#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 20);
push(&head, 4);
push(&head, 15);

/* Create a loop for testing */
head->next->next = head;
detectloop(head);

getchar();
}

Time Compelxity O(n)
Space Compelxity O(1)

2nd Algorithm
Brent Algorithm For Loop Detection in Linked List

#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int findLoop(struct node* head)
{
if (head == NULL)
return 0;
struct node* slow = head;
struct node* fast = head;
int i = 0;
int k = 1;

while (slow != NULL)
{
slow = slow->next;
i++;
if (slow == fast)
return 1;
if (i == k)
{
fast = slow;
k*= 2;
}
}
return 0;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 20);
push(&head, 4);
push(&head, 15);

/* Create a loop for testing */
head->next->next = head;
printf(" %d ",findLoop(head));

getchar();
}

Time Compelxity O(n)
Space Compelxity O(1)

Both Above Algos are basically used to detct cycle in Graph.

Algorithm for Removing loop From Linked List

This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

Working Code For Removing Loop

#include
#include

/* Link list node */
struct Node
{
int value;
struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data */
new_node->value= new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void removeloop(struct Node *head)
{

struct Node *p1 = NULL, *p2 = NULL;

while(head)
{
if (p1 == NULL && p2 == NULL)
{
// 1. Two pointers start from head

p1 = head;
p2 = head;
}
else
{
// 2 If two pointers meet, there is a loop

if (p1 == p2)
break;
}

// 3 If pointer reachs the end, there is no loop
if (p2->next == NULL || p2->next->next == NULL)
{
printf("There is no loop in the list.\n");
return ;
}

// 4. One pointer advances one while the other advances two.
p1 = p1->next;
p2 = p2->next->next;
}

// 5. Find out how many nodes in the loop, say k.

unsigned int k = 1;
p2 = p2->next;
while (p1 != p2)
{
p2 = p2->next;
k++;
}
printf("There are %d nodes in the loop of the list.\n", k);

// 6. Reset one pointer to the head, and the other pointer to head + k.
p1 = head;
p2 = head;

for (unsigned int i = 0; i < k; i++) p2 = p2->next;

// 7. Move both pointers at the same pace, they will meet at loop starting node
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}

printf("node %d is the loop starting node.\n", p1->value);

// 8. Move one of the pointer till its next node is the loop starting node.
// It's the loop ending node
p2 = p2->next;
while(p2->next != p1)
p2 = p2->next;

printf("node %d is the loop ending node.\n", p2->value);
// 9. Set the next node of the loop ending node to fix the loop
p2->next = NULL;

}

/* Utility function to print a linked list */
void printList(struct Node *head)
{
while(head!=NULL)
{
printf("%d ",head->value);
head=head->next;
}
printf("\n");
}


int main()
{
/* Start with the empty list */
struct Node *head = NULL;

push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);

head->next->next->next->next->next=head->next->next;

removeloop(head);

printList(head);

printf("\n");
}

Time Compelxity O(n)
Space Compelxity O(1)
Run Here https://ideone.com/wN4tR
You can Have a Look at http://ostermiller.org/find_loop_singly_linked_list.html

WAP to Find Minimum Distance Between Two Elements in An Array, Containg Duplicate As Well

Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1.

Data Structure :Array

Algorithm:take variables current=-1 & min=INT_Max
so we start from last element say its index is last which is array size -1 & check it with a & b if its equal to any of these then check current !=- && a[current]!=a[last] if its true then compare min with min & current-last & update the min e.g min=minimum(min,current-last)
set current=n; repeat until we run out of loop

#include
#include
int min(int a,int b)
{ if( a
#include

void minDistance (int* pArray, int size, int num1, int num2, int* firstIndex, int* secIndex)
{
int curDst=0, minDst=INT_MAX, index1=0, index2=0;
int moveFirst=1, moveSec = 1;



while ((index1 index2)
{
moveFirst = 0;
moveSec = 1;
curDst = index1 - index2;
if (curDst < minDst)
{
minDst = curDst;
*firstIndex = index2-1;
*secIndex = index1-1;
}
}
else
{
moveFirst = 1;
moveSec = 0;
curDst = index2 - index1;
if (curDst < minDst)
{
minDst = curDst;
*firstIndex = index1-1;
*secIndex = index2-1;
}
}
}
}


int main ()
{
int array [] = {2,2,4,1,8,3,2,5,6,7,5,6,6,4,7,5};
int index1=0, index2=0;
minDistance (array, 16, 6, 2, &index1, &index2);
printf ("Index1 = %d, Index2 = %d\n", index1, index2);
printf ("Minimum distance b|w given num = %d\n", index2-index1);
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
RUN Here https://ideone.com/EL8CX

WAp to Count Inversion Count In an Array Linear Time

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

METHOD 1 (Simple)
For each element, count number of elements which are on right side of it and are smaller than it.
?
int getInvCount(int arr[], int n)
{
int inv_count = 0;
int i, j;

for(i = 0; i < n - 1; i++)
for(j = i+1; j < n; j++)
if(arr[i] > arr[j])
inv_count++;

return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
int arr[] = {1, 20, 6, 4, 5};
printf(" Number of inversions are %d \n", getInvCount(arr, 5));
getchar();
return 0;
}

Time Complexity: O(n^2)

Method2 Using BST

#include
using namespace std;

struct node{
int data;
node *left;
node *right;
int rc;
};

node *root = NULL;

int get_inv(int val)
{
node *newnode = new node;
newnode -> data = val;
newnode -> left = NULL;
newnode -> right = NULL;
newnode -> rc = 0;

int inv = 0;

if(!root)
{
root = newnode;
return 0;
}

node *ptr = root;
node *pptr = root;
while(ptr)
{
pptr = ptr;
if(val < ptr->data)
{
inv += ptr->rc +1;
ptr = ptr->left;
}
else
{
ptr->rc++;
ptr = ptr->right;
}
}

if(val < pptr->data)
{
pptr->left = newnode;
}
else
{
pptr->right = newnode;
}

return inv;
}

int count_inv(int *array,int n)
{
int inv = 0;
for(int i=0;i {
inv += get_inv(array[i]);
}
return inv;
}

int main()
{
int array[] = {3,6,1,2,4,5};
cout< return 0;
}
Run Here https://ideone.com/Ghvop
Solution Provided by Naman
Time Complexity O(n(logn))

WAP to Find Kth Maximum or Kth Minimum in Array in Linear Time

Other Variation

You have to develop a piece of code that can be attached to a program
like Microsoft Word, which would list the last "N" words of the
document in descending order of their occurrence, and update the list
as the user types. What code would you write? Using pseudo code is
fine, just list the basic things you would consider

Given a stream of distance of millions of stars from the earth, find the nearest n star from the earth.


Algorithm

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
a) If the element is greater than the root then make it root and call heapify for MH
b) Else ignore it.
O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)



Java Code


class Heap_new
{
int arr[]; // pointer to array of elements in heap
int heap_size;
Heap_new()
{

}

Heap_new(int a[], int size)
{
heap_size = size;
arr = a;
}


int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;

void changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void swap(int i,int j)
{
int temp=i;
i=j;
j=temp;
}

void minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
minHeapify(largest);
}
}

void buildminHeap()
{
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap_new hp=new Heap_new(arr,k);
hp.buildminHeap();

int i;
for(i = k; i < n; i++)
{
changeRoot(arr[i]);
}

}

public static void main(String a[])
{
int k = 4;
int arr[] = new int[]{12, 34, 10, 8, 9, 24, 66};
Heap_new h=new Heap_new();
h.kthLargest(arr,arr.length,k);
int i=0;
for(i=0;iSystem.out.println(arr[i]);

}


}



Run Here https://ideone.com/UKAzU

C++ Code for Kth Maximum In Array


#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildminHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}

}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 22, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
kthLargest(arr, n, k);


int i=0;
for(i=0;iprintf(" %d ",arr[i]);

getchar();
return 0;
}


Run here https://ideone.com/f8Or0

C++ Code For Kth Minimum In Array

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildmaxHeap();
void maxHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root > x)
{
arr[0] = x;
}
maxHeapify(0);
}

void Heap::maxHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] >arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
maxHeapify(largest);
}
}

void Heap::buildmaxHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
maxHeapify(i);
i--;
}
}

int kthMinimum(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildmaxHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}
return hp.getRoot();
}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
printf(" %d ", kthMinimum(arr, n, k));
int i=0;
for(i=0;i printf(" %d ",arr[i]);

getchar();
return 0;
}

Run Here https://ideone.com/JIu1s

Source Sandeep
Enjoy

minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
minHeapify(largest);
}
}

A long time ago, in a very remote island known as Lilliput, society was split into two factions: Big-Endians who opened their soft-boiled eggs at the larger end ("the primitive way") and Little-Endians who broke their eggs at the smaller end. As the Emperor commanded all his subjects to break the smaller end, this resulted in a civil war with dramatic consequences: 11.000 people have, at several times, suffered death rather than submitting to breaking their eggs at the smaller end. Eventually, the 'Little-Endian' vs. 'Big-Endian' feud carried over into the world of computing as well, where it refers to the order in which bytes in multi-byte numbers should be stored, most-significant first (Big-Endian) or least-significant first (Little-Endian) to be more precise [1]

* Big-Endian means that the most significant byte of any multibyte data field is stored at the lowest memory address, which is also the address of the larger field.
* Little-Endian means that the least significant byte of any multibyte data field is stored at the lowest memory address, which is also the address of the larger field.

For example, consider the 32-bit number, 0xDEADBEEF. Following the Big-Endian convention, a computer will store it as follows:

Big-Endian

Figure 1. Big-Endian: The most significant byte is stored at the lowest byte address.

Whereas architectures that follow the Little-Endian rules will store it as depicted in Figure 2:

Little-Endian

Figure 2. Little-endian: Least significant byte is stored at the lowest byte address.

The Intel x86 family and Digital Equipment Corporation architectures (PDP-11, VAX, Alpha) are representatives of Little-Endian, while the Sun SPARC, IBM 360/370, and Motorola 68000 and 88000 architectures are Big-Endians. Still, other architectures such as PowerPC, MIPS, and Intel�s 64 IA-64 are Bi-Endian, i.e. they are capable of operating in either Big-Endian or Little-Endian mode. [1].

Endianess is also referred to as the NUXI problem. Imagine the word UNIX stored in two 2-byte words. In a Big-Endian system, it would be stored as UNIX. In a little-endian system, it would be stored as NUXI.
Which format is better?

Like the egg debate described in the Gulliver's Travels, the Big- .vs. Little-Endian computer dispute has much more to do with political issues than with technological merits. In practice, both systems perform equally well in most applications. There is however a significant difference in performance when using Little-Endian processors instead of Big-Endian ones in network devices (more details below).
How to switch from one format to the other?

It is very easy to reverse a multi-byte number if you need the other format, it is simply a matter of swapping bytes and the conversion is the same in both directions. The following example shows how an Endian conversion function could be implemented using simple C unions:
Collapse

unsigned long ByteSwap1 (unsigned long nLongNumber)
{
union u {unsigned long vi; unsigned char c[sizeof(unsigned long)];};
union v {unsigned long ni; unsigned char d[sizeof(unsigned long)];};
union u un;
union v vn;
un.vi = nLongNumber;
vn.d[0]=un.c[3];
vn.d[1]=un.c[2];
vn.d[2]=un.c[1];
vn.d[3]=un.c[0];
return (vn.ni);
}

Note that this function is intented to work with 32-bit integers.

A more efficient function can be implemented using bitwise operations as shown below:
Collapse

unsigned long ByteSwap2 (unsigned long nLongNumber)
{
return (((nLongNumber&0x000000FF)<<24)+((nLongNumber&0x0000FF00)<<8)+
((nLongNumber&0x00FF0000)>>8)+((nLongNumber&0xFF000000)>>24));
}

And this is a version in assembly language:
Collapse

unsigned long ByteSwap3 (unsigned long nLongNumber)
{
unsigned long nRetNumber ;

__asm
{
mov eax, nLongNumber
xchg ah, al
ror eax, 16
xchg ah, al
mov nRetNumber, eax
}

return nRetNumber;
}

A 16-bit version of a byte swap function is really straightforward:
Collapse

unsigned short ByteSwap4 (unsigned short nValue)
{
return (((nValue>> 8)) | (nValue << 8));

}

Finally, we can write a more general function that can deal with any atomic data type (e.g. int, float, double, etc) with automatic size detection:
Collapse

#include //required for std::swap


#define ByteSwap5(x) ByteSwap((unsigned char *) &x,sizeof(x))

void ByteSwap(unsigned char * b, int n)
{
register int i = 0;
register int j = n-1;
while (i {
std::swap(b[i], b[j]);
i++, j--;
}
}

For example, the next code snippet shows how to convert a data array of doubles from one format (e.g. Big-Endian) to the other (e.g. Little-Endian):
Collapse

double* dArray; //array in big-endian format

int n; //Number of elements


for (register int i = 0; i ByteSwap5(dArray[i]);

Actually, in most cases, you won't need to implement any of the above functions since there are a set of socket functions (see Table I), declared in winsock2.h, which are defined for TCP/IP, so all machines that support TCP/IP networking have them available. They store the data in 'network byte order' which is standard and endianness independent.
Function Purpose
ntohs Convert a 16-bit quantity from network byte order to host byte order (Big-Endian to Little-Endian).
ntohl Convert a 32-bit quantity from network byte order to host byte order (Big-Endian to Little-Endian).
htons Convert a 16-bit quantity from host byte order to network byte order (Little-Endian to Big-Endian).
htonl Convert a 32-bit quantity from host byte order to network byte order (Little-Endian to Big-Endian).

Table I: Windows Sockets Byte-Order Conversion Functions [2]

The socket interface specifies a standard byte ordering called network-byte order, which happens to be Big-Endian. Consequently, all network communication should be Big-Endian, irrespective of the client or server architecture.

Suppose your machine uses Little Endian order. To transmit the 32-bit value 0x0a0b0c0d over a TCP/IP connection, you have to call htonl() and transmit the result:
Collapse

TransmitNum(htonl(0x0a0b0c0d));

Likewise, to convert an incoming 32-bit value, use ntohl():
Collapse

int n = ntohl(GetNumberFromNetwork());

If the processor on which the TCP/IP stack is to be run is itself also Big-Endian, each of the four macros (i.e. ntohs, ntohl, htons, htonl) will be defined to do nothing and there will be no run-time performance impact. If, however, the processor is Little-Endian, the macros will reorder the bytes appropriately. These macros are routinely called when building and parsing network packets and when socket connections are created. Serious run-time performance penalties occur when using TCP/IP on a Little-Endian processor. For that reason, it may be unwise to select a Little-Endian processor for use in a device, such as a router or gateway, with an abundance of network functionality. (Excerpt from reference [1]).

One additional problem with the host-to-network APIs is that they are unable to manipulate 64-bit data elements. However, you can write your own ntohll() and htonll() corresponding functions:

* ntohll: converts a 64-bit integer to host byte order.
* ntonll: converts a 64-bit integer to network byte order.

The implementation is simple enough:
Collapse

#define ntohll(x) (((_int64)(ntohl((int)((x << 32) >> 32))) << 32) |
(unsigned int)ntohl(((int)(x >> 32)))) //By Runner

#define htonll(x) ntohll(x)

How to dynamically test for the Endian type at run time?

As explained in Computer Animation FAQ, you can use the following function to see if your code is running on a Little- or Big-Endian system:
Collapse

#define BIG_ENDIAN 0
#define LITTLE_ENDIAN 1

int TestByteOrder()
{
short int word = 0x0001;
char *byte = (char *) &word;
return(byte[0] ? LITTLE_ENDIAN : BIG_ENDIAN);
}

This code assigns the value 0001h to a 16-bit integer. A char pointer is then assigned to point at the first (least-significant) byte of the integer value. If the first byte of the integer is 0x01h, then the system is Little-Endian (the 0x01h is in the lowest, or least-significant, address). If it is 0x00h then the system is Big-Endian.

Similarly,
Collapse

bool IsBigEndian()
{
short word = 0x4321;
if((*(char *)& word) != 0x21 )
return true;
else
return false;
}

which is just the reverse of the same coin.

You can also use the standard byte order API�s to determine the byte-order of a system at run-time. For example:
Collapse

bool IsBigEndian() { return( htonl(1)==1 ); }

Auto detecting the correct Endian format of a data file

Suppose you are developing a Windows application that imports Nuclear Magnetic Resonance (NMR) spectra. High resolution NMR files are generally recorded in Silicon or Sun Workstations but recently Windows or Linux based spectrometers are emerging as practical substitutes. It turns out that you will need to know in advance the Endian format of the file to parse correctly all the information. Here are some practical guidelines you can follow to decipher the correct Endianness of a data file:

1. Typically, the binary file includes a header with the information about the Endian format.
2. If the header is not present , you can guess the Endian format if you know the native format of the computer from which the file comes from. For instance, if the file was created in a Sun Workstation, the Endian format will most likely be Big-Endian.
3. If none of the above points apply, the Endian format can be determined by trial and error. For example, if after reading the file assuming one format, the spectrum does not make sense, you will know that you have to use the other format.

If the data points in the file are in floating point format (double), then the _isnan() function can be of some help to determine the Endian format. For example:
Collapse

double dValue;
FILE* fp;
(...)
fread(&nValue, 1, sizeof(double), fp);
bool bByteSwap = _isnan(dValue) ? true : false

Note that this method does only guarantee that the byte swap operation is required if _isnan() returns a nonzero value (TRUE); if it returns 0 (FALSE), then it is not possible to know the correct Endian format without further informatio

WAP to Find Mean,Median,Mod of Array

/***************************************************************
******* Program to find Mean,Median,and Mode *******
****************************************************************/

#define SIZE 100
#include
float mean_function(float[],int);
float median_function(float[],int);
float mode_function(float[],int);

int main()
{

int i,n,choice;
float array[SIZE],mean,median,mode;
printf("Enter No of Elements\n");
scanf("%d",&n);
printf("Enter Elements\n");
for(i=0;i
scanf("%f",&array[i]);

do
{

printf("\n\tEnter Choice\n\t1.Mean\n\t2.Median\n\t3.Mode\n4.Exit");
scanf("%d",&choice);
switch(choice)
{

case 1:

mean=mean_function(array,n);
printf("\n\tMean = %f\n",mean);
break;

case 2:

median=median_function(array,n);
printf("\n\tMedian = %f\n",median);
break;

case 3:

mode=mode_function(array,n);
printf("\n\tMode = %f\n",mode);
break;

case 4:

break;

default:

printf("Wrong Option");
break;

}

}while(choice!=4);

}



/***************************************************************
Function Name : mean_function
Purpose : to find mean
Input : array of elements,no of elements
Return Value : Mean
Return Type : Float
****************************************************************/

float mean_function(float array[],int n)
{

int i;
float sum=0;
for(i=0;i
sum=sum+array[i];

return (sum/n);

}

/***************************************************************
Function Name : median_function
Purpose : to find median
Input : array of elements,no of elements
Return Value : Median
Return Type : Float
****************************************************************/

float median_function(float a[],int n)
{

float temp;
int i,j;
for(i=0;i
for(j=i+1;j{

if(a[i]>a[j])
{

temp=a[j];
a[j]=a[i];
a[i]=temp;

}

}

if(n%2==0)
return (a[n/2]+a[n/2-1])/2;
else
return a[n/2];

}

float mode_function(float a[],int n)
{

return (3*median_function(a,n)-2*mean_function(a,n));

}



Output
————–

Enter Elements
2
3
4

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1

Mean = 3.000000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2

Median = 3.000000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3

Mode = 3.000000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4

——————-
Enter No of Elements
4
Enter Elements
9 8 7 6

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1

Mean = 7.500000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2

Median = 7.500000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3

Mode = 7.500000

Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4

WAP to Find Level Order Successor of Node in Binary Tree

1) Using the parent pointer, get the level of the given node. Also, get the root of the tree.

int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
/* temp is now root of the tree and level is level of the node */

2) Once we have level of the given node and root of the tree, traverse the tree from root to the calculated level + 1. We are traversing one extra level for the case when given node is the rightmost node of its level. While traversing if you visit the given node, mark visited flag as 1. Print the node just after the visited flag.


#include
#include

/* Note the structure of root. It has data and pointers to left childe, right child and
parent node */
struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};

/* Prints the level order successor of node
root --> root of the tree
level --> level of node */
void _print(struct node* root, struct node *node, int level)
{
static int visited = 0;
if(root == NULL)
return;
if(level == 1 || level == 1)
{
/* If the given node is visited then print the current root */
if(visited == 1)
{
printf("Level Order Successor is %d ", root->data);
visited = 0;
return;
}
/* If the current root is same as given node then change the visited flag
so that current node is printed */
if(root == node)
visited = 1;
}
else if (level > 1)
{
_print(root->left, node, level-1);
_print(root->right, node, level-1);
}
}

void printLevelOrderSuccessor(struct node *node)
{
int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
_print(temp, node, level);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->parent = NULL;
root->left = newNode(2);
root->right = newNode(3);
root->left->parent = root;
root->right->parent = root;

root->left->left = newNode(4);
root->right->right = newNode(5);

root->left->left->parent = root->left;
root->right->right->parent = root->right;

// printf("\n Level order successor of %d is: ", root->right->data);
printLevelOrderSuccessor(root->left->left);

getchar();
return 0;
}

Source Geeks4Geeks

WAP to Do Level Order Successor of Tree

1) Using the parent pointer, get the level of the given node. Also, get the root of the tree.

int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
/* temp is now root of the tree and level is level of the node */

2) Once we have level of the given node and root of the tree, traverse the tree from root to the calculated level + 1. We are traversing one extra level for the case when given node is the rightmost node of its level. While traversing if you visit the given node, mark visited flag as 1. Print the node just after the visited flag.


#include
#include

/* Note the structure of root. It has data and pointers to left childe, right child and
parent node */
struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};

/* Prints the level order successor of node
root --> root of the tree
level --> level of node */
void _print(struct node* root, struct node *node, int level)
{
static int visited = 0;
if(root == NULL)
return;
if(level == 1 || level == 1)
{
/* If the given node is visited then print the current root */
if(visited == 1)
{
printf("Level Order Successor is %d ", root->data);
visited = 0;
return;
}
/* If the current root is same as given node then change the visited flag
so that current node is printed */
if(root == node)
visited = 1;
}
else if (level > 1)
{
_print(root->left, node, level-1);
_print(root->right, node, level-1);
}
}

void printLevelOrderSuccessor(struct node *node)
{
int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
temp = temp->parent;
level++;
}
_print(temp, node, level);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->parent = NULL;
root->left = newNode(2);
root->right = newNode(3);
root->left->parent = root;
root->right->parent = root;

root->left->left = newNode(4);
root->right->right = newNode(5);

root->left->left->parent = root->left;
root->right->right->parent = root->right;

// printf("\n Level order successor of %d is: ", root->right->data);
printLevelOrderSuccessor(root->left->left);

getchar();
return 0;
}

Source Geeks4Geeks

WAP To generate New random Function Using Another Given Random number function

You are given a random no. generator function rand04() that generates
random numbers between 0 and 4 (i.e., 0,1,2,3,4) with equal
probability. You have to design a random no. generator function
rand07() that generates numbers between 0 to 7 (0,1,2,3,4,5,6,7) using
rand04() such that rand07() generates all numbers between 0 to 7 with
equal probability.

import java.util.*;
class rand05
{

static int rand04()
{
Random r=new Random();
return (r.nextInt(5));
}

static int rand07()
{
int r;
do {
r = rand04() + 5 * rand04(); // 0 to 24.
} while (r >= 8 * 3);
return r / 3;

}



public static void main(String a[])
{
System.out.println(rand07());

}


}

Some Explanation

rand04() rand04() 5*rand04() Sum Sum/3
0 0 0 0 0
1 0 0 1 0
2 0 0 2 0
3 0 0 3 1
4 0 0 4 1
0 1 5 5 1
1 1 5 6 2
2 1 5 7 2
3 1 5 8 2
4 1 5 9 3
0 2 10 10 3
1 2 10 11 3
2 2 10 12 4
3 2 10 13 4
4 2 10 14 4
0 3 15 15 5
1 3 15 16 5
2 3 15 17 5
3 3 15 18 6
4 3 15 19 6
0 4 20 20 6
1 4 20 21 7
2 4 20 22 7
3 4 20 23 7
4 4 20 24 8

As you can see, each of the numbers from


Source & Great Info. http://www.ihas1337code.com/2010/11/rejection-sampling.html

Whehn This Loop Will Stop ..A very important Question

Question Given Below

float f1 = 0.0f, f2;
do
{
f2 = f1;
f1 = f1 + 1;
}
while (f2 != f1);


what will the o/p of this question & why its more important why..??

O/P 1.677722e+7



About Floats
Computers, CPUs, and electronic devices store numbers in binary format. Floating
point numbers, or floats, are the most commonly used system for representing real
numbers in computers. In industrial automation applications, analog values read
from an I/O unit are an example of floats. Floats represent real numbers in scientific
notation: as a base number and an exponent.
The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) is the most widely
used standard for floating-point computation. It defines how to store real numbers
in binary format and how to convert between binary and float notations.
Opto 22’s SNAP PAC System uses IEEE single-precision floats, which have 32 binary
digits (bits). The IEEE 754 32-bit float format is as follows:
Float calculation: (-1)Sign x [1 + Significand/223] x 2 (Exponent-127)
While this is an excellent standard for the purpose, it has limitations that could cause
issues if you’re not aware of them. Squeezing infinitely many real numbers into a
finite number of bits requires an approximate representation. Most floats cannot be
exactly represented using this fixed number of bits in a 32-bit IEEE float. Because of
this, rounding error is inherent in floating-point computation.
In PAC Control (and in PAC Manager and the OptoMMP protocol), a float is a 32-bit
IEEE single-precision number ranging from ±3.402824 x 10-38 to ±3.402824 x
10+38. These single-precision floats give rounding errors of less than one part per
million (1 PPM). You can determine the limit of the rounding error for a particular
float value by dividing the value by 1,000,000.
This format guarantees about six and a half significant digits. Therefore,
mathematical actions involving floats with seven or more significant digits may incur
errors after the sixth significant digit. For example, if the integer 555444333 is
converted to a float, the conversion yields 5.554444e+8 (note the error in the 7th
digit). Also, converting 5.554444e+8 back to an integer yields 555444352 (note the
error starting in the 7th digit).
Float Issues and Examples
Accumulation of Relatively Small Floating-point Values
When adding float values, the relative size of the two values is important. For
example, if you add 1.0 to a float variable repeatedly, the value of the float variable
will correctly increase in increments of 1.0 until it reaches 1.677722e+7 (16,777,220).
1 bit 8 bits 23 bits
x xxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx
Sign Exponent Significand
Using Floats Technical Note
PAGE
2 TECHNICAL NOTE • Form 1755-080130
Then the value will no longer change, because 1.0 is too small relative to 1.677722e+7 to
make a difference in the significant digits. The same thing will occur if you add 0.0001 to
2,048.0, or add 1,000.0 to 1.717987e+10. The key is the relative size of the numbers.
Here’s another way to think of it. Suppose your bank could only keep track of seven digits. If
you were fortunate enough to have one million dollars ($1,000,000) in your account and
tried to add 10 cents ($0.10) to it, you would not be able to, because the 10 cents is not big
enough relative to the total to be significant. Since the bank has only seven digits to keep
track of your money (in this example), one digit has to fall off the end: either the 10 cents
falls off the right side or the million digit falls off the left side. Which would you rather see in
your bank account?
Note that moving the point indicator doesn’t help, because the exponent is separate. If the
seven digits for the account represent millions of dollars (1.000000) rather than dollars
(1,000,000), the 10 cents would be 0.0000001—still too small to be represented by the
seven digits:
The key is that it is not the size of the numbers that matter, but rather their relative size.
So if you are accumulating relatively small values in a float variable over a long period of
time, at some point, the float value will stop increasing even though you continue to try to
add to it.
Comparing Floating-point Values for Equality
Due to rounding errors and the way floating-point calculations are performed, comparing
two floats for equality can yield inaccurate results. The precision of comparisons depends
on the relative size of the float values as compared to the difference between them.
For example, if 2,097,151.0 is compared for equality with 2,097,152.0, the result will
indicate that the two floats are equal, even though it’s obvious they are not. The reason is
that the difference between the two values is 1.0, and 1.0 compared to one of the
compared values (2,097,151.0) is too small; it is less than one part per million.
In this case, 2,097,152.0 divided by 1,000,000 is 2.1. If the difference between the two
values is at least 2.1, then the equality comparison is guaranteed to be correct. So if
2,097,152.0 and 2,097,149.0 were compared for equality, the result will indicate they are
not equal, because the difference (3.0) is greater than one part per million (2.1). Any time
Seven digits available: 1 2 3 4 5 6 7
Amount in account: 1 0 0 0 0 0 0
Add 10 cents (0.10)? (digit falls off on right) 1 0 0 0 0 0 0
Add 10 cents (0.10)? (digit falls off on left) 0 0 0 0 0 0. 1 Oops!
Seven digits available: 1 2 3 4 5 6 7
Amount in account 1. 0 0 0 0 0 0
Add 10 cents (0.0000001)? (digit falls off on right) 1. 0 0 0 0 0 0
Add 10 cents (0.0000001)? (digit falls off on left) .0 0 0 0 0 0 1 Oops again!
Using Floats Technical Note
PAGE
TECHNICAL NOTE • Form 1755-080130 3
the difference is at least one part per million, the result is guaranteed to be accurate. If the
difference is less than 1 PPM, it may or may not be accurate.
One method that programmers use to work around this issue is to subtract one float from
the other and then compare the absolute value of the result to a limit.
For example:
Float_Diff = Float1 - Float2;
If (AbsoluteValue(Float_Diff) < 1.0 ) then
SetVariableTrue(EqualityFlag);
Else
SetVariableFalse(EqualityFlag);
Endif


Source http://www.opto22.com/documents/1755_Using_Floats_Technical_Note.pdf