You have a note to write by cutting and pasting necessary letters from the book, write an algorithm to see if you can write the note.

import java.util.*;
import java.io.*;

public class NoteChecker
{

private final File noteFile;
private final File bookFile;

private int noteTotalLength = 0;

private void checkIfFileExists(File file)
{
if( ! file.exists() )
{
throw new IllegalArgumentException("File doesn't exists '" + file.getPath() + "'");
}
}

public NoteChecker(String noteFilePath, String bookFilePath){
super();

noteFile = new File(noteFilePath);
checkIfFileExists(noteFile);

bookFile = new File(bookFilePath);
checkIfFileExists(bookFile);
}

private int[] getRequiredLetters()
{

final int[] requiredLetters = new int[128];

Scanner noteSc = null;

try{

noteSc = new Scanner(noteFile);

while( noteSc.hasNextLine() ){
String line = noteSc.nextLine();

for(int i =0; i < line.length(); i++ ){
char ch = line.charAt(i);
++requiredLetters[ch];
++noteTotalLength;
}
}
}
catch(Exception ex ){
ex.printStackTrace();
return requiredLetters;
}
finally {
if( noteSc != null ){
noteSc.close();
}
}

return requiredLetters;
}

public boolean canCreateNote()
{

final int[] requiredLetters = getRequiredLetters();

Scanner bookSc = null;

try
{

bookSc = new Scanner(bookFile);

while( bookSc.hasNextLine() )
{
String line = bookSc.nextLine();

for(int i =0; i < line.length() && noteTotalLength > 0; i++ )
{
char ch = line.charAt(i);

if( requiredLetters[ch] > 0 )
{
--requiredLetters[ch];
--noteTotalLength;
}
}
}
}
catch(Exception ex)
{

ex.printStackTrace();
return false;
}
finally
{
if( bookSc != null )
{
bookSc.close();
}
}
return noteTotalLength == 0 ? true : false;
}



public static void main(String a[])
{

NoteChecker ob=new NoteChecker("E:/ubuntu/note.txt","E:/ubuntu/Input.txt");
System.out.println(ob.canCreateNote());


}
}
Above Solution is provided By Max

TC O(m+n)
SC O(1)

WAP to Find Maximum and minimum of an array using minimum number of comparisons

Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.

First of all, how do we return multiple values from a C function? We can do it either using structures or pointers.

We have created a structure named pair (which contains min and max) to return multiple values.

?
struct pair
{
int min;
int max;
};
And the function declaration becomes: struct pair getMinMax(int arr[], int n) where arr[] is the array of size n whose minimum and maximum are needed.


Method 1

Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element)

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;

/*If there is only one element then return it as min and max both*/
if(n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}

/* If there are more than one elements, then initialize min
and max*/
if(arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[0];
minmax.min = arr[1];
}

for(i = 2; i {
if(arr[i] > minmax.max)
minmax.max = arr[i];

else if(arr[i] < minmax.min)
minmax.min = arr[i];
}

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Time Complexity: O(n)
Space Complexity O(1)
Run Here https://ideone.com/yFZNJ

In this method, total number of comparisons is 1 + 2(n-2) in worst case and 1 + n – 2 in best case.
In the above implementation, worst case occurs when elements are sorted in descending order and best case occurs when elements are sorted in ascending order.



METHOD 2 (Tournament Method) (Efficient)

Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.

Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Implementation

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;

/* If there is only on element */
if(low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}

/* If there are two elements */
if(high == low + 1)
{
if(arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);

/* compare minimums of two parts*/
if(mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;

/* compare maximums of two parts*/
if(mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Number of Instruction Executed less
Time Complexity: O(n)
Space Complexity
Run Here https://ideone.com/jB3tu

Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
If n is a power of 2, then we can write T(n) as:

T(n) = 2T(n/2) + 2
After solving above recursion, we get

T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.

WAP to generate the Dyck Word from given string.??

A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's

It Can Be Solved by Catalan Number Cn=2nCn/(n+1)=2n!/n!*n+1!

Cn is the number of Dyck words of length 2n. A For example, the following are the Dyck words of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.


class DyckWord
{
public static void printDyckWord(int xnum, int ynum, char[] str, int count)
{
if (xnum < 0 || ynum < xnum) return; // invalid state
if (xnum == 0 && ynum == 0)
{
System.out.println(str); // found one, so print it
}
else
{
if (xnum > 0) { // try a left paren, if there are some available
str[count] = 'X';
printDyckWord(xnum - 1, ynum, str, count + 1);
}
if (ynum > xnum) { // try a right paren, if there’s a matching left
str[count] = 'Y';
printDyckWord(xnum, ynum - 1, str, count + 1);
}
}
}

public static void printDyckWord(int count)
{
char[] str = new char[count*2];//As DyckWord is 2n length nX + nY
printDyckWord(count, count, str, 0);
}
public static void main(String a[])
{
printDyckWord(3);
}
}

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

WAP to Calculate the next Smallest Prime Number From Given Number Efficiently

Given a number n, compute the smallest prime that is bigger than n. For example, n=8, then the smallest prime that bigger than 8 is 11. n=23 o/p is 29 & so on

#include

int power(int x, int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


double sqrt(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}

int next_prime(int n)
{
int i=n+1;


/*The largest known Mersenne prime (243,112,609 − 1) is also the largest known prime
number,else // no such prime exist explain above
int pow=power(2,243112609)−1;
if(n>pow)
return 0; this line wont execute overflow*/

while(true)
{

if(is_prime(i))
break;
i++;

}
return i;
}
int main()
{
printf( " %d ", next_prime(23));
return 0;

}


TC of isprime is O(sqrt(n))
TC of sqrt is log(n)
TC of pow function is O(logn)
TC of next prime O(k*sqrt(n) where k is number of iteration used to find next smallest prime so k is constant & so overall time complexity of this algo is O(sqrt(n))

TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/5ViQe

Feel Free to Comment or Optimize the solution or if any issue with time complexity

WAP find Minimum Distance Between two Nodes In Binary Tree

Algorithm

Assume each node has parent pointer:
let distance d=0;
1. Start from the node 1 and find the distance of the node from root by traversing up. let it be d1.
2. start from node 2 and do the same. let this distance be d2.
3.if(d1>d2) then traverse d1-d2 nodes up from the node2. add d=d+(d1-d2)
4.now traverse up from each node from that place until both point to same node. while traversing up make d=d+2;
5. when both reaches to same node, it represents the common ancestor. so substract 1 from d.
6. now d represents the distance between two nodes.

Algo Suggested By sreenivas putta then I Coded It.

Efficiency Level:- Not Efficient (cause Parent Pointer Overhead)

#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;
struct node* parent;
};

/* 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);
}

int distance(struct node* root, struct node* n1,struct node* n2)
{
int d=0,d1=0,d2=0;
struct node* temp=n1;

while(temp->parent!=NULL)
{
temp=temp->parent;
d1++;

}
temp=n2;

while(temp->parent!=NULL)
{
temp=temp->parent;
d2++;

}
if(d1>d2)
{

d=d1-d2;
while((d1-d2)>0)
{

n1=n1->parent;
d1--;
}

}
else
{
d=d2-d1;
while((d2-d1)>0)
{
n2=n2->parent;
d2--;
}

}
while(n1!=n2)
{

n1=n1->parent;
n2=n2->parent;
d+=2;

}
return d;

}

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

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

/* then recur on left sutree */
printPreorder(node->left);

/* now recur on right subtree */
printPreorder(node->right);
}

/* 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->left->right = newNode(5);
root->left->left->parent=root->left;
root->left->right->parent=root->left;

root->left->left->left = newNode(6);
root->left->left->right = newNode(7);
root->left->left->left->parent= root->left->left;
root->left->left->right->parent= root->left->left;

root->left->right->left = newNode(8);
root->left->right->right = newNode(9);
root->left->right->left->parent= root->left->right;
root->left->right->right->parent= root->left->right;

root->right->left = newNode(10);
root->right->right = newNode(11);
root->right->left->parent=root->right;
root->right->right->parent=root->right;


root->right->left->left = newNode(12);
root->right->left->right = newNode(13);
root->right->left->left->parent=root->right->left;
root->right->left->right->parent=root->right->left;

root->right->right->left = newNode(14);
root->right->right->right = newNode(15);
root->right->right->left->parent=root->right->right;
root->right->right->right->parent=root->right->right;

//printf("\n Preorder traversal of binary tree is \n");
//printPreorder(root);

printf( " %d ", distance(root, root->left->left->left , root->right->right->right));

getchar();
return 0;
}

TC O(n)
Sc O(1)
Run Here https://ideone.com/aFNsP

Design The Data Structure & Algorithm to Show That Their Exist a Path (Connection Between Two Person on Facebook)

How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection,
or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).


Approach:
Forget that we’re dealing with millions of users at first. Design this for the simple case.
We can construct a graph by assuming every person is a node and if there is an edge between
two nodes, then the two people are friends with each other.
class Person {
Person[] friends;
// Other info
}
If I want to find the connection between two people, I would start with one person and do a simple breadth first search.
But... oh no! Millions of users!
When we deal with a service the size of Orkut or Facebook, we cannot possibly keep all of our data on one machine. That means that our simple Person data structure from above doesn’t quite work—our friends may not live on the same machine as us. Instead, we can replace our list of friends with a list of their IDs, and traverse as follows:
1. For each friend ID: int machine_index = lookupMachineForUserID(id);
2. Go to machine machine_index
3. Person friend = lookupFriend(machine_index);
There are more optimizations and follow up questions here than we could possibly discuss, but here are just a few thoughts.
Optimization: Reduce Machine Jumps
Jumping from one machine to another is expensive. Instead of randomly jumping from machine
to machine with each friend, try to batch these jumps—e.g., if 5 of my friends live on one machine, I should look them up all at once.
Optimization: Smart Division of People and Machines
People are much more likely to be friends with people who live in the same country as them. Rather than randomly dividing people up across machines, try to divvy them up by country, city, state, etc. This will reduce the number of jumps.
Question: Breadth First Search usually requires “marking” a node as visited. How do you do that in

this case?
Usually, in BFS, we mark a node as visited by setting a flag visited in its node class. Here, we don’t want to do that (there could be multiple searches going on at the same time, so it’s bad to just edit our data). In this case, we could mimic the marking of nodes with a hash table to lookup a node id and whether or not it’s been visited.
Other Follow-Up Questions:
»»In the real world, servers fail. How does this affect you?
»»How could you take advantage of caching?
»»Do you search until the end of the graph (infinite)? How do you decide when to give up?
»»In real life, some people have more friends of friends than others, and are therefore more likely to make a path between you and someone else. How could you use this data to pick where you start traversing?
The following code demonstrates our algorithm:

import java.util.*;

public class Server
{
ArrayList machines = new ArrayList();
}

public class Machine {
public ArrayList persons = new ArrayList();
public int machineID;
}

public class Person {
private ArrayList friends;
private int ID;
private int machineID;
private String info;
private Server server = new Server();

public String getInfo() { return info; }
public void setInfo(String info) {
this.info = info;
}

public int[] getFriends() {
int[] temp = new int[friends.size()];
for (int i = 0; i < temp.length; i++) {
temp[i] = friends.get(i);
}
return temp;
}
public int getID() { return ID; }
public int getMachineID() { return machineID; }
public void addFriend(int id) { friends.add(id); }

// Look up a person given their ID and Machine ID
public Person lookUpFriend(int machineID, int ID)
{
for (Machine m : server.machines)
{
if (m.machineID == machineID)
{
(Person p : m.persons)
{
if (p.ID == ID){
return p;
}
}
}
}
return null;
}

// Look up a machine given the machine ID
public Machine lookUpMachine(int machineID)
{
for (Machine m:server.machines)
{
if (m.machineID == machineID)
return m;
}
return null;
}

public Person(int iD, int machineID)
{
ID = iD;
this.machineID = machineID;
}

}

Algorithm & Solution Given By Galye

WAP to Find Maximum Difference between two Index of array such that value at 1st index is less then value at 2nd Index, Efficiently

WAP to find out maximum j-i such that a[i]
Method 1

Algorithm
Use two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.


#include
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
struct maxdif
{
int i;
int j;
int maxDiff;

};
struct maxdif maxIndexDiff(int a[],int n)
{
struct maxdif maxdif;
maxdif.maxDiff=-1;
int i=0,j=0;
for(i=0;i {
for(j=n-1;j>0;j--)
{
if(a[i] {
maxdif.i=i;
maxdif.j=j;
maxdif.maxDiff=j-i;
}
}
}
return maxdif;
}

int main()
{ int ar[]={9,2,3,4,5,6,7,8,20,1};
int n=sizeof(ar)/sizeof(int);
struct maxdif max_diff=maxIndexDiff(ar,n);
printf(" j=%d i=%d maximum difference=%d", max_diff.j,max_diff.i,max_diff.maxDiff);
return 0;
}

Worst Case O(n^2)
Input: {1, 2, 3, 4, 5, 6}
Output: 5 (j = 5, i = 0)

Best Case O(n)
Input: {6, 5, 4, 3, 2, 1}
Output: -1

Time Complexity: O(n^2)
Space Complexity O(1)
Run Here https://ideone.com/lzIEd

Method 2 (Algorithm Given By Celicom


Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(jwhile(B[i] < C[j] && jmax_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}

so To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.


#include
 
/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}
 
int min(int x, int y)
{
    return x < y? x : y;
}
 
/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;
 
    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);
 
   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);
 
    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);
 
    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }
 
    return maxDiff;
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {9,2,3,4,5,6,7,8,20,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}


Time Complexity O(n)
Space Complexity O(n)
Ryun Here https://ideone.com/vQOMi

WAP to Implement Add,Subtract,Multiplication,Division Using Bit Manipulation

1st Approach to do the all operation

Addition

Here we use, One’s Complement Operator (~ - Known as Tilda). This is a Unary Operator. The output of “~b” means, One Complement of the value stored in ‘b’. For example, a=10, b=5. Then the ~b=-6. This operator simply works on the binary value of the corresponding Integer. As we know, One’s Complement is nothing but the Interchange of the 1’s and 0’s. So, If we give Input as b=5. The binary equivalent of 5 = 0000 0101 (Here we Consider that size of the Integer is 1 byte = 8 bits). Then the Complement of 5 = 1111 1010.Here the Most important thing is the Negative Numbers are stored in Computer as Two’s Complement Form. 2’s Complement = 1’s Complement + 1, And 1 111 1010, here the Left Most bit Represents the Sign of the Number, 1 indicates Negative, 0 Indicates Positive. So, Two’s Complement of 111 1010 is 000 0110 = 6, and of course, it is the Negative Number, so ~5 = -6. And Apply in the Expression, a-~b-1 = 10–(-6)-1 = 10+6–1 = 15. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sum;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sum = a - ~b - 1; /* For the Explanation, See the Comments on Top */

printf("\nSum : %d",sum);
getch();
}

Subtraction
The Only difference here is the interchage of operators. Thats All.

For example, Assume that a=10, b=5. We know the difference is 5. Here we use the ‘~’ Operator in b. So ~b = – 6. Then a + ~b + 1 = 10 +(-6)+1 = 5. Simple Expression, But with Logic.

#include
#include

void main()
{
int a,b,sub;
clrscr();

printf("Enter 2 No.s : ");
scanf("%d%d",&a,&b); // Read 2 Integers

sub = a + ~b + 1; /* For the Explanation, See the Comments on Top */

printf("\nSubtraction : %d",sub);
getch();
}

Multiplication

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to add the First Number, for Second Number Times. That’s All.

For example, Assume that a=5, b=4. We know the Answer is 20. Here we need to do is Adding the Number 5 itself,for 4 times. So We get the Answer as 20.

For better performance always add the Big Number,for Small Number Times. For Example to Multiply 5 * 100, better we Add 100,for 5 times, rather than adding 5, for 100 times.

#include
#include

void main()
{
int i,a,b,mul,big,small;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(a>b) // To find which is the Big one to Add Small one Times
{
big=a;
small=b;
}

else
{
big=b;
small=a;
}

mul=0; // Initialize the Variable to zero for Storing the Answer.

 for(i=1;i<=small;i++) // Adding Big Number, for Small Number Times. 
 {
     mul+=big; 
     printf("\n%d Times %d = %d",i,big,mul); 
 }
     printf("\n\nThe Answer is %d",mul); getch();
} 

 Division

This One is the Simply Logical. This will work all kind of Inputs. The concept behind this is We need to Perform the Reverse Operation performed on the Mutiplication Without '*' Opreator. Here we need to Subtract the Second Number From the First Number Until First Number >= Second Number. That’s All.

For example, Assume that a=10, b=3. Here we need to do is Subtract the Number 3 from the number 10 itself, until a>=b. And we should make a count for how many times we are doing like this, It is the Quotient Value.

So, finally We get the Answer as 3 Times we subtract 3 from the Number 10. Because we are checking the Condition a>=b everytime. So the is the Quotient as 3. The Remainder will be stored itself in 'a' as 1.

#include
#include

void main()
{
int a,b,c;
clrscr();

printf("Enter 2 No.s :\n");
scanf("%d%d",&a,&b); // Read 2 Numbers

if(b==0) // Here we are Checking for the Divide By Zero Error
{
printf("\nDivide By Zero Error");
}

else
{
c=0; // Here c as Count, and we should initialize the Count value to 0.
while(a>=b) // We Repeatedly Checking for the Condition a>=b
{
a = a - b; // Subtract b from a, and the new result stored in 'a' itself
c++; // Incrementing the Count
}

printf("\nQuotient = %d \n Remainder = %d",c,a); // Print Quotient and Remainder
}

getch();
}


Pure Low level Implementation (Bit Manipulation)

Lets Try For Decimal Integer Number how we add them

1 Add 759 + 674, but “forget” to carry I then get 323
2 Add 759 + 674 but only do the carrying, rather than the addition of each digit I then
get 1110
3 Add the result of the first two operations (recursively, using the same process de-
scribed in step 1 and 2): 1110 + 323 = 1433

we have done for decimal numbers

Now, how would we do this in binary?

1 If I add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and
b are both 0 or both 1 This is an XOR
2 If I add two numbers together but only carry, I will have a 1 in bit[i] if bit[i-1] in a and b
are both 1’s This is an AND, shifted

3 Now, recurse until there’s nothing to carry

int add_no_arithm(int a, int b)
{
if (b == 0) return a;
int sum = a ^ b; // add without carrying
int carry = (a & b) << 1; // carry, but don’t add return add_no_arithm(sum, carry); // recurse 
 }

 Subtraction int sub(int x, int y)
{
      return(add(x,add(~y,1));

}

 Multiplication m=0;
 while (a)
 {
     if (a&1)
      m+=b; a>>=1;
     b<<=1; 
 }
printf("%d\n",m); The above code is a implementation of an algorithm better known as the Ethiopian 

Multiplication or the Russian Peasant Multiplication. Here’s the algorithm : 
 1. Let the two numbers to be multiplied be a and b. 
 2. If a is zero then break and print the result. 
 3. If a is odd then add b to the result. 
 4. Half a, Double b. Goto Step 2.

 Algorithm For Division :
 Given a dividend and a divisor would be to left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. This is similar to finding an element in a sorted list using the binary search algorithm, the C code is furnished below. #include

int dividend=17, divisor=2 , remainder;

int division(int tempdividend, int tempdivisor) 
{
int quotient = 1;

if (tempdivisor == tempdividend) {
remainder = 0;
return 1;
} else if (tempdividend < tempdivisor) { remainder = tempdividend; return 0; } while (tempdivisor <= tempdividend) { /* Here divisor < dividend, therefore left shift (multiply by 2) divisor and quotient */ tempdivisor = tempdivisor << 1; quotient = quotient << 1; } /* We have reached the point where divisor > dividend,
therefore divide divisor and quotient by two */
tempdivisor = tempdivisor >> 1;
quotient = quotient >> 1;

printf("\n %d %d", dividend, divisor);

/* Call division recursively for the difference to get the
exact quotient */
quotient = quotient + division(tempdividend - tempdivisor, divisor);

return quotient;
}

/* Division of two numbers without using division operator */
int main()
{
printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

}

Run Here https://ideone.com/aSbGn

Source
http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

WAP to Remove Loop From Doubly Linked List Efficiently

Algorithm


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.

Note:One Test case Not Covered That I Will Do Later it Involve Prev Pointer




#include
#include

struct node
{
int data;
struct node *next;
struct node *prev;
};

/* Function to remove loop. */
int removeLoop(struct node *, struct node *);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
int removeLoop(struct node *loop_node, struct node *head)
{
struct node *ptr1 = loop_node;
struct node *ptr2 = loop_node;

// Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2)
{
ptr1 = ptr1->next;
k++;
}

// Fix one pointer to head
ptr1 = head;

// And the other pointer to k nodes after head
ptr2 = head;
for(i = 0; i < k; i++)
ptr2 = ptr2->next;

/* Move both pointers at the same pace,
they will meet at loop starting node */
while(ptr2 != ptr1)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

// Get pointer to the last node
ptr2 = ptr2->next;
while(ptr2->next != ptr1)
ptr2 = ptr2->next;

/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}

/* UTILITY FUNCTIONS */
/* Given a reference (pointer to pointer) to the head
of a list and an int, pushes a new node on the front
of the list. */
/* 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 linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

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

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

detectAndRemoveLoop(head);

printf("Linked List after removing loop \n");
printList(head);

getchar();
return 0;
}

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

WAP to Detect Loop In Doubly Linked List

Algorithm : Floyd’s Cycle-Finding 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. Apart from above case one more cases may arises.

Case 1 : Whole link list is in loop. It Means last node points to first node. This can be solved by using two pointers. one pointer points to given node in link list and another pointers loops around the link list
If (Given_node == node->next) or or if(fast->prev=slow->prev)  Explained Above

Case 2: Part of link list is in loop
If (node->next != node->next->next->prev) is true means double link list is a loop.

 Time Complexity Will be O(N) N is length of Linked List




#include
#include

struct node
{
int data;
struct node *next;
struct node *prev;
};

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

while(slow_p && fast_p &&
fast_p->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (fast_p->prev==slow_p->prev|| slow_p == fast_p) //Look Closely !!!!!!!!!!!!!!!
{
printf("Found Loop");
return 1;
}

}
return 0;
}

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

new_node->data = new_data;

prev is always NULL */
new_node->prev = NULL;

new_node->next = (*head_ref);

if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

(*head_ref) = new_node;
}

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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, 4);
push(&head, 8);
push(&head, 10);

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

//head->next->next->next=head->next; //1st test case
// head->next=head;//2nd test case //head->prev=head not necessary
head->next->next->prev=head;// 3rd Test Case
/* similarly we can do it using prev pointer for this we have to go to last node first the
start form its prev pointer .. so making the loop in program is our choice it depnds how we
connects them using prev & next pointer */

detectLoop(head);


//printf("\n After Looping Doubly Linked list ");
//printList(head); //Testing Purpose Only

getchar();
}

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