You have a string "RGBBGBGR". Eliminate the pairs (two same chars adjacent to each other) recursively.

Example:
RGBBGBGR --> RGGBGR-->RBGR
Answer: Here recursively mean not a recursive function but to do it in the manner shown in example. Still we can do it recursively like below:

Fun_rcur(string)
{
if pairs
Remove pairs in string
Fun_recur(string)
Else
Return
}

But this is very costly:
1) Extra space (stack space for recursive calls)
2) You need to go through entire string in each recursive call.

Lets see an iterative approach for the same. We should check if we have character pair then cancel it and then check for next character and previous element. Keep canceling the characters until you either reach start of the array, end of the array or not find a pair.



C Code Complexity O(N^2) & Space O(1) Recursion

#include
#include
void couple_remove(char []);
int main(){
char arr[]="RGBBGBGR";// "RGBBGBGRRGRR";
couple_remove(arr);
printf("\n\n%s\n\n", arr);
return 0;
}

void couple_remove(char arr[]){
int remove=0,i,j;
int len=strlen(arr);
for(i=0;i if( arr[i]== arr[i+1] ){
for(j=i+2;j<=len;j++) {
arr[i]=arr[j];
i++;
remove=1;
}
}
if ( remove )
break;
}
if ( remove )
couple_remove(arr);
}

Rune Here https://ideone.com/urZEo


Java Code Complexity O(n) & Space O(n) Iterative

import java.util.Stack;
class CoupleElimination {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack st = new Stack();
String inputString = "RGBBGBGR";
for( int i=0 ; i < inputString.length() ; i++ )
{
char ch = inputString.charAt(i);
char top ;
if( !st.empty())
{
top = st.peek();

if( top == ch)
st.pop();
else
st.push(ch);
}

else
st.push(ch);
}
String result = "";
while( !st.empty() )
{
result = st.pop()+result;
}
System.out.println(result);
}
}

Run Here https://ideone.com/UF0Ao

WAP to Given a doubly linked list with just 3 numbers 0,1,2 . Sort it

Only Important Part is This Its Tricky to Solve
Traverse list and count '0', '1' and '2'. (O(N))

int zerosCount = 10;
int onesCount = 5;
int twosCount = 4;

Traverse list and fill according to counters. (O(N))

Time: O(N)
Space: O(1)


/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


struct node* sort(struct node *head)
{
struct node* current=head;
struct node* temp=NULL;
if (current!= NULL)
{
int zeroCount = 0;
int oneCount = 0;
int twoCount = 0;

//Find out the count for 0, 1 and 2
while(current!=NULL)
{
if (current->data == 0) {
zeroCount++;
} else if (current->data == 1) {
oneCount++;
} else if (current->data == 2) {
twoCount++;
}
else
{
break;
}
current=current->next;
}

//Fill a based on counts of 0, 1 and 2

temp=head;
for (int i = 0; i < zeroCount; i++)
{
temp->data = 0;
temp=temp->next;

}
for (int i = 0; i < oneCount; i++) {
temp->data = 1;
temp=temp->next;
}
for (int i = 0; i < twoCount; i++) {
temp->data = 2;
temp=temp->next;
}
}
temp=head;
return temp;
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
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;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

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

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

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

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);


sort(head);

printf("\n Original Linked list ");
printList(head);


getchar();
}
Not Efficient Because it Requires 3 Paas Over Array
TC O(n)
SC O(1)
Run Here https://ideone.com/XdipA


As You Can See Above method Will take More Instruction to Execute , because it requires same thing to be do in three pass can't we do in single pass . yeas there exist an algorithm Named 3-Way Partioning or Dutch National Flag Algorithm , so that we can finish it in single pass & can make program more efficient.

But Above Algo Requires Mid points to be calculated , Again & Again until Array or list is not empty ..so think getting the mid point in array can be done in O(1) & for n items we repeat the things & can be done in O(logn) because we know starting & ending of array but what to do in-case of linked list calculating the mid point will take O(logn) & for n item this algo will take O(nlogn) ..ohh we are beyond of limit ..we din't expected this Time for an O(n) Solution...but we can add some pointer overhead for maintaining start & end location of o,1,2 & then in finally we can append 1's to 2's & 2's to 3's isn't ..yes it will work & we have done

so Algorithms is

1 Divide the list into 3 different lists,
2 list0 having all 0's, list2 having all 1's and list2 having all 2's
3 Concatenate list0, list1 and list2


2nd Method Implementation

/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


struct node* sort(struct node *head)
{
struct node* current=head;
struct node* start0=NULL;
struct node* start1=NULL;
struct node* start2=NULL;
struct node* n0=NULL;
struct node* n1=NULL;
struct node* n2=NULL;

if(!current)
return NULL;


while(current)
{
switch(current->data)
{
case 0:
if(n0)
{
n0->next=current;
}
else
{
start0=current;
}
n0=current;
break;

case 1:
if(n1)
{
n1->next=current;
}
else
{
start1=current;
}
n1=current;
break;

case 2:
if(n2)
{
n2->next=current;
}
else
{
start2=current;
}
n2=current;
break;
}
current=current->next;
}



if(n0)
n0->next=start1;
if(n1)
n1->next=start2;
if(n2)
n2->next=NULL;

return start0;


}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
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;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

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

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

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

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);


head=sort(head);

printf("\n Sorted Linked list ");
printList(head);


getchar();
}

Advantage Sorting Can Be Done in Single Pass
TC O(n)
SC O(1)
Run Here https://ideone.com/clone/Ny3OI


Feel Free to Comment if you Find Anything Wrong Above..??

WAP to Program The Combinations of Number That Sums Up to Given Traget Number..Print Unique Combinations Only

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)


Solution:
To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate={2,3,6,7} and target=7.

First, we start with a sum of 0. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum={2,3,6,7}. Assume now that sum=2, we continue adding all possible candidate numbers {2,3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

We stop when the sum is greater than the target sum. Why? Remember our earlier assumption that candidate numbers must all be positive? Since the candidate array contains only positive numbers, if we continue searching, we would only add larger numbers to the sum, and this would not help us achieving the target sum. The other case where we stop is when the sum is equal to the target sum. We have found a valid combination.


#include
using namespace std;

void printSum(int candidates[], int index[], int n) {
for (int i = 1; i <= n; i++)
cout << candidates[index[i]] << ((i == n) ? "" : "+");
cout << endl;
}

void solves(int target, int sum, int candidates[], int sz, int index[], int n) {
if (sum > target)
return;
if (sum == target)
printSum(candidates, index, n);

for (int i = index[n]; i < sz; i++) {
index[n+1] = i;
solves(target, sum + candidates[i], candidates, sz, index, n+1);
}
}

void solve(int target, int candidates[], int sz) {
int index[10000];
index[0] = 0;
solves(target, 0, candidates, sz, index, 0);
}

int main()
{
int a[]={2,3,6,7};
solve(7,a,4);

}

I Discussed It with My Friend Ashim kapoor & after that we are able to solve4 it without repeatation

2nd Method

#define MAX_POINT 4
#define ARR_SIZE 100
#include

/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int arr[ARR_SIZE],int n, int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
// static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(arr,n-k, i+1);
}
}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i,flag=1;

for (i = 0; i < arr_size; i++)
if(arr[i]>arr[i+1]) flag=0;
if(flag)
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
int arr[ARR_SIZE]={1,2,3,4};
printCompositions(arr,n, 0);
getchar();
return 0;
}

Run Here https://ideone.com/NCrkD


Java Code for doing the same.

class PrintAllCombi {



/**
* @param args
*/
public static void main(String[] args) {
int s = 6;
int[] a = new int[] {2,3,6,7,8};
getCombi(a, 0, s, 0, "");
}

private static void getCombi(int[] a, int j, int s, int currentSum, String st) {
if(s == currentSum) {
System.out.println(st);
return;
}
if(currentSum > s) {
return;
}
for(int i=j; igetCombi(a, i, s, currentSum+a[i], st+"+"+a[i]);
}
}


}

Run Here https://ideone.com/XiWAF

Dominator of an array ...Majority Element In Different Way

Majority Element Different Possible Solutions


Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O() = O(nlogn) complexity. #try it

Solution 3 Using BitCount Array

#include
int findmaj(int arr[], int n)
{
int bitcount[32];
int i, j, x;

for(i = 0; i < 32; i++)
bitcount[i] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < 32; j++)
if (arr[i] & (1 << j)) // if bit j is on
bitcount[j]++;
else
bitcount[j]--;

x = 0;
for (i = 0; i < 32; i++)
if (bitcount[i] > 0)
x = x | (1 << i);
return x;
}

int main()
{
int i;
int arr[5] = {1, 3 ,1, 1, 3};

printf(" %d ", findmaj(arr, 5));

getchar();
return 0;
}

We keep a count of frequency of each of the bits. Since majority element will dominate the frequency count, hence we can get its value.

The solution is constant space and linear time : O(n)

Method 4 (Using Binary Search Tree)

Node of the Binary Search Tree (used in this approach) will be as follows. ?
struct tree
{
int element;
int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)

METHOD 5 (Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element. Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "NONE"

# include<stdio.h>
# define bool int

int findCandidate(int *, int);
bool isMajority(int *, int, int);

void printMajority(int a[], int size)
{
int cand = findCandidate(a, size);

if(isMajority(a, size, cand))
printf(" %d ", cand);
else
printf("NO Majority Element");
}

int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}

int main()
{
int a[] = {1, 3, 3, 1,1,1,2,3,1,2,1,1};
printMajority(a, 12);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space : O(1)
Run Here http://ideone.com/ALf5fY

Amplitude of Element In Unsorted Array

/*
The amplitude of a non-empty zero-indexed array A consisting of N numbers is defined as

amplitude(A) = max { A[P] - A[Q] : 0 <= P, Q < N }

Write a function

int amplitude(int[] A);

that given a non-empty zero-indexed array A consisting of N non-negative integers returns its amplitude. Assume that the length of the array does not exceed 1,000,000. Assume that each element of the array is a non-negative integer not exceeding 5,000,000.

For example, given array A such that

A[0]=10, A[1]=2, A[2]=44, A[3]=15, A[4]=39, A[5]=20

the function should return 42.

*/

Java Code

class array
{
public static void main(String a[])

{

System.out.println(amplitude(new int[]{10, 2, 44, 15, 39, 20}));

}

static int amplitude ( int[] A )
{
// write your code here
int min=A[0];
int max=A[0];
int diff=0;

if(A==null)
return 0;
if(A.length==0)
return 0;

if(A.length>1000000)
{
return 0;
}
else
{

for(int i=0;i {
if(A[i] min=A[i];
if(A[i]>max)
max=A[i];

diff=max-min;
}

}
return diff;
}

}

Ugly Number e.g. Numer Whose prime Factor are 2 or 3 or

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150′th ugly number.

1st Method

using namespace std;
#define MAXSIZE 15
 
int minimum(int x,int y,int z)
{
    if (x      return (y}
 
int nextUgly(int nth)//nth
{
    int num2,num3,num5;
    int ugly[MAXSIZE], ptr2, ptr3, ptr5;
        ugly[0]=1;int i=0;
        ptr2=ptr3=ptr5=0;
 
   for(i=1;i  {
    num2=ugly[ptr2]*2;
    num3=ugly[ptr3]*3;
    num5=ugly[ptr5]*5;
 
    ugly[i]=minimum(num2,num3,num5);
 
    if(ugly[i]==num2) ptr2++;
    if(ugly[i]==num3) ptr3++;
    if(ugly[i]==num5) ptr5++;
 
   }
 
    return ugly[nth-1];
}
 
int main()
{
 
    printf("15th Ugly number is %d\n",nextUgly(15));
}


TC O(n)
SC O(1)

2nd Method

Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.

To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.

For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.


# include
# include

/*This function divides a by greatest divisible
power of b*/
int maxDivide(int a, int b)
{
while (a%b == 0)
a = a/b;
return a;
}

/* Function to check if a number is ugly or not */
int isUgly(int no)
{
no = maxDivide(no, 2);
no = maxDivide(no, 3);
no = maxDivide(no, 5);

return (no == 1)? 1 : 0;
}

/* Function to get the nth ugly number*/
int getNthUglyNo(int n)
{
int i = 1;
int count = 1; /* ugly number count */

/*Check for all integers untill ugly count
becomes n*/
while (n > count)
{
i++;
if (isUgly(i))
count++;
}
return i;
}

/* Driver program to test above functions */
int main()
{
unsigned no = getNthUglyNo(150);
printf("150th ugly no. is %d ", no);
getchar();
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/zyBWV

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