int atoi( char* pStr ) {
int iRetVal = 0;
if (pStr)
{
while ( *pStr && *pStr <= '9' && *pStr >= '0' )
{
iRetVal = (iRetVal * 10) + (*pStr - '0');
pStr++;
}
}
return iRetVal;
}
If we allow -ve and + signs we need to take care of them as well in the out put and check for invalid characters.
Saturday, September 3, 2011
Atoi
Check if array elements are consecutive
The idea is to check for following two conditions. If following two conditions are true, then return true.
1) max – min + 1 = n where max is the maximum element in array, min is minimum element in array
and n is the number of elements in array.
2) All elements are distinct.
To check if all elements are distinct, we can create a visited[] array of size n.
We can map the ith element of input array arr[] to visited array by using arr[i] – min as index in visited[].
Majority Element
A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
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 , answer : 2.
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"
Searching a pivot in the sorted rotated array
Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength – 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
Solution:
This time you have to search for the rotation pivot. There is a subtle observation. This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.
1 2 3 4 5 6 7 8 9 10 11 12 13 | int FindSortedArrayRotation(int A[], int N) { int L = 0; int R = N - 1; while (A[L] > A[R]) { int M = L + (R - L) / 2; if (A[M] > A[R]) L = M + 1; else R = M; } return L;} |
Some Test Cases:
{ 1 }
return 0
return 0
{ 1, 2 }
return 0
{ 2, 1 }
return 1
{ 1, 2, 3 }
return 0
{ 3, 1, 2 }
return 1
{ 2, 3, 1 }
return 2
{ 1, 2, 3, 4, 5 }
return 0
{ 2, 3, 4, 5, 1 }
return 4
{ 3, 4, 5, 1, 2 }
return 3
{ 4, 5, 1, 2, 3 }
return 2
{ 5, 1, 2, 3, 4 }
return 1
{ 1, 2, 3, 4, 5, 6 }
return 0
{ 2, 3, 4, 5, 6, 1 }
return 5
{ 3, 4, 5, 6, 1, 2 }
return 4
{ 4, 5, 6, 1, 2, 3 }
return 3
{ 5, 6, 1, 2, 3, 4 }
return 2
{ 6, 1, 2, 3, 4, 5 }
return 1
{ 6, 8, 1, 2, 4, 5 }
return 2
Searching an Element in a Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently?
At first look, we know that we can do a linear search in O(n) time. But linear search does not need the elements to be sorted in any way.
First, we know that it is a sorted array that’s been rotated. Although we do not know where the rotation pivot is, there is a property we can take advantage of. Here, we make an observation that a rotated array can be classified as two sub-array that is sorted (i.e., 4 5 6 7 0 1 2 consists of two sub-arrays 4 5 6 7 and 0 1 2.
Do not jump to conclusion that we need to first find the location of the pivot and then do binary search on both sub-arrays. Although this can be done in O(lg n) time, this is not necessary and is more complicated.
In fact, we don’t need to know where the pivot is. Look at the middle element (7). Compare it with the left most (4) and right most element (2). The left most element (4) is less than (7). This gives us valuable information — All elements in the bottom half must be in strictly increasing order. Therefore, if the key we are looking for is between 4 and 7, we eliminate the upper half; if not, we eliminate the bottom half.
When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.
Since we reduce the search space by half each time, the complexity must be in the order of O(lg n). It is similar to binary search but is somehow modified for this problem. In fact, this is more general than binary search, as it works for both rotated and non-rotated arrays.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | int rotated_binary_search(int A[], int N, int key) { int L = 0; int R = N - 1; while (L <= R) { // Avoid overflow, same as M=(L+R)/2 int M = L + ((R - L) / 2); if (A[M] == key) return M; // the bottom half is sorted if (A[L] <= A[M]) { if (A[L] <= key && key < A[M]) R = M - 1; else L = M + 1; } // the upper half is sorted else { if (A[M] < key && key <= A[R]) L = M + 1; else R = M - 1; } } return -1;} |
Segregate even and odd nodes in a Linked List
Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear
before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.
Method 1
The idea is to get pointer to the last node of list. And then traverse the list starting from the head node and
move the odd valued nodes from their current position to end of the list.
Algorithm:
1) Get pointer to the last node.
2) Move all the odd nodes to the end.
a) Consider all odd nodes before the first even node and move them to end.
b) Change the head pointer to point to the first even node.
c) Consider all odd nodes after the first even node and move them to the end.
Implement Queue using Stacks
A queue can be implemented using two stacks.
Let queue to be implemented be q and stacks used to implement q be stack1 and stack2.
q can be implemented in two ways:
Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1,
so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1.
In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.
Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation,
while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Queue can also be implemented using one user stack and one Function Call Stack.
Below is modified Method 2 where recursion is used to implement queue using only one user defined stack.
enQueue(x)
1) Push x to stack1.
deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item
in a variable res, push the res back to stack1 and return res
The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step 3.
Levenshtein Distance
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)x(n+1) values
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i // the distance of any first string to an empty second string
for j from 0 to n
d[0, j] := j // the distance of any second string to an empty first string
for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}
return d[m,n]
}
|
|
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Example : 10,12, 20,30, 25,40,32,31,35,50,60
1) Find the candidate unsorted subarray
a) Scan from left to right and find the first element which is greater than the next element.Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order).Let e be the index of such an element.In the above example 1, e is 7 (index of 31).
2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.There is no such element in above example 1.
c) Find first element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.In the above example 1,e is changed to 8 (index of 35)
3) Print s and e.
Find the pair from an sorted array whose difference is x
Here is an inplace solution with O(n) complexity.
i=0,j=1;
while((i!=n-1) or j!=n)
{
/*compare difference of a[j] and a[i]*/
if( (a[j]-[a[i]])>x ) {
i++;j++;
}
else if( (a[j]-a[i]) {
j++;
}
else
{
/*SOLUTION*/
return;
}
}
Find 10 maximum integer out of 1 million integers
You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That. What is Time & space Complexity of Algorithm that you will use then optimize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyte of memory may be required so that should be avoided. Answer: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want.
Find whether given tree is a subtree or not
Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
Pseudo code :
check( node t1 , node t2 )
{
if ( t1->data == t2->data)
{
return check( t1->left , t2->left ) && check(t1->right, t2->right) ;
}
else
{
return check(t1->left , t2) || check(t1->right , t2);
}
}
Time complexity :O(n) because each node in T1 needs to be visited once.
Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array
Given an array of integers, each element represents the max number of jumps can make forward.
What is the minimum number of element selections to reach the end of the array (starting from the first element) ?
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps
Implementation : Using Dynamic programming -
int find_min_steps(int arr[], int n)
{
// min_steps_dp[i] is an array which
// indicate minimum jumps required to reach i.
int min_steps_dp[20];
int i, temp, next_vacant;
// next_vacant : Is the index in the array whose min_steps needs to be updated
// in the next iteration.
next_vacant = 1;
for(i=0;i= n)
{
min_steps_dp[n-1] = min(min_steps_dp[n-1],min_steps_dp[i] +1);
}
else
{
min_steps_dp[temp] = min(min_steps_dp[temp],min_steps_dp[i]+1);
}
if(temp>next_vacant)
{
for(;next_vacant<temp;next_vacant++)
{
// this loop executes only ONCE for each element in the array, so over the
// course of execution, is an O(n) loop only.
min_steps_dp[next_vacant] =min(min_steps_dp[next_vacant],min_steps_dp[temp]);
}
}
}
for(i=0;i<n;i++)
{
printf("%d ",min_steps_dp[i]);
}
return min_steps_dp[n-1];
}
main()
{
int arr[] = {1,3,5,8,9,2,6,7,6,8,9};
int len;
len = sizeof(arr)/sizeof(arr[0]);
printf("\n MIN steps : %d\n",find_min_steps(arr,len));
}
Friday, September 2, 2011
Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3).
Using the maximum value and its coordinates, we can find out the required sub-matrix.
#include
#define bool int
#define R 6
#define C 5
void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming
How to find whether two Strings are Anagrams or not
Method 1 : Scan first one and compute sum and product of the ASCII character codes. Do the same for the other and compare the sums and products. You are computing two different hashcodes that are position invariant and by doing a sum and a product, you are reducing a chance of a collision. Overflow (esp in case of product) increases the chances of collision. Method 2 : Just take an array of 256 length and initialize with 0. Now,traverse string1 and just increment the value at index=ascii code of character. Then traverse string2, and this time decrement. At any point if time, if you get -1 then you can break. If you dont find so, then traverse the whole array again to check if all locations are zero then they are anagram. Method 3 : Sort both the strings and compare with each other , if both are same then they are Anagrams else not.
Permutations for a given number
Below are the permutations of string ABC. ABC, ACB, BAC, BCA, CAB, CBA Here is a solution using backtracking./* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } /* Driver program to test above functions */ int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } Algorithm Paradigm: Backtracking Time Complexity: O(n!)
Pair of indices such that A[i] 十A[j] =K in given Array
Design an efficient algorithm for determining if there exist
a pair of indices such that A[i] 十A[j] =K.
Normal way would cost us O(n^2) complexity. But using Hashing complexity reduces to O(n).
Second approach is to while parsing the array find the complement (K - arr[i]) . Store the array index in to a hash table. In the hash table we search for the complement. if the complement exist, it returns it.
sub pairsum(arr, K)
{
H={}; // Hash array initialize to zero.
for i in range(arr, len)
complement = K - arr[i];
H[arr[i]] = i; // Store the index of array element.
if(H[complement])
return H[complement], arr[i];
}
Inorder Tree Traversal without recursion and without stack!
A threaded binary tree may be defined as follows:
"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node."
A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.
It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly.
This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
Although the tree is modified through the traversal, it is reverted back to its original shape after the completion.Unlike Stack based traversal, no extra space is required for this traversal.
Implementation :
/* A binary tree tNode has data, pointer to left child and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Function to traverse binary tree without recursion and without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
MorrisTraversal(root);
getchar();
return 0;
}
Find two non repeating elements in the given array which contains all repeated elements except two
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Method 1(Use Sorting)
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn)
Method 2(Use XOR)
Let x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.
xor = arr[0]^arr[1]^arr[2].....arr[n-1]
All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.
Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.
Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of
elements in each set, and we get the non-repeating
elements 7 and 9.
Implementation:
#include
#include
/* This finction sets the values of *x and *y to nonr-epeating
elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
*x = 0;
*y = 0;
/* Get the xor of all elements */
for(i = 1; i < n; i++)
xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i < n; i++)
{
if(arr[i] & set_bit_no)
*x = *x ^ arr[i]; /*XOR of first set */
else
*y = *y ^ arr[i]; /*XOR of second set*/
}
}
/* Driver program to test above function */
int main()
{
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int *x = (int *)malloc(sizeof(int));
int *y = (int *)malloc(sizeof(int));
get2NonRepeatingNos(arr, 8, x, y);
printf(" The non-repeating elements are %d and %d", *x, *y);
getchar();
}
Time Complexity: O(n)
Auxiliary Space: O(1)
Explanation :
XOR of two same numbers results in 0(000..00)
XOR of two different numbers x and y results in a number which contains set bits at the places where x and y differ. So if x and y are 10...0100 and 11...1001, then result would be 01...1101.
So the idea is to XOR all the elements in set.In the result xor, all repeating elements would nullify each other. The result would contain the set bits where two non-repeating elements differ.
Now, if we take any set bit of the result xor and again do XOR of the subset where that particular bit is set, we get the one non-repeating element.And for other non-repeating element we can take the subset where that particular bit is not set.
We have chosen the rightmost set bit of the xor as it is easy to find out.
How to check whether given number is prime or not
Primality Test
Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime. However, rather than testing all m up to n − 1, it is only necessary to test m up to root of n. if n is composite then it can be factored into two values, at least one of which must be less than or equal to root of n. The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does. It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.
Method to find Square Root
Algorithm:
This method can be derived from (but predates) Newton–Raphson method.
1 Start with an arbitrary positive start value x (the closer to the
root, the better so take x=n/2) .
2 Initialize y = 1.
3. Do following until desired approximation is achieved.
a)Get the next approximation for root using average of x and y
b)Set y = n/x
Implementation:
/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
/*We are using n itself as initial approximation
This can definitely be improved */
float x = n/2; //n/2 can be closest one.
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}
/* Driver program to test above function*/
int main()
{
int n = 50;
printf ("Square root of %d is %f", n, squareRoot(n));
getchar();
}
Example:
n = 4 /*n itself is used for initial approximation*/
Initialize x = 4, y = 1
Next Approximation x = (x + y)/2 (= 2.500000),
y = n/x (=1.600000)
Next Approximation x = 2.050000,
y = 1.951220
Next Approximation x = 2.000610,
y = 1.999390
Next Approximation x = 2.000000,
y = 2.000000
Terminate as (x - y) > e now.
For a perfect square number this e would be equal to 0.
Given an array and a sum S output all combination of elements that sum to S
Example: 1 2 3
sum = 3
1+1+1,
2+1
3
Program:
int arr[] = {1,2,3};
void printcombination(int n, int index, int i)
{
static int a[100];
int j;
// sum is equal to zero print all numbers that form the sum.
if(n == 0)
{
for(j =0;j 0)
{
for(j = i; j < 3;j++)
{
a[index] = arr[j];
// call printcombination only when the difference is greater than or equal to zero
if(n-arr[j] >= 0)
printcombination(n-arr[j], index + 1, j);
}
}
}
main()
{
int sum = 3;
printcombination(sum, 0, 0);
return 0;
}
Find the Missing Number
You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
Example:
I/P [1, 2, 4, ,6, 3, 7, 8]
O/P 5
METHOD 1(Use sum formula)
Algorithm:
1. Get the sum of numbers
total = n*(n+1)/2
2 Subtract all the numbers from sum and
you will get the missing number.
METHOD 2(Use XOR)
1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.
Thursday, September 1, 2011
Pattern matching in given String
KMP Algorithm : KMP Algo
To see how to construct failure function examples refer Examples for constructing failure function
To see how to construct failure function examples refer Examples for constructing failure function
Find common elements in an Array
Suppose two arrays are given , we need to find the common elements. case 1 : two arrays are sorted . case 2 : two arrays are unsorted . Answer : case 1 : Do a search as we just move through them as we would merge them. As they are sorted , while searching the element in the 2nd array with the element in the 1st array , we can store the index where it the 1st array element exceeds the 2nd array element. Such that the next search can begin at this stored index. case 2 : Hash both the arrays , wherever collision occurs its a common element.
Tree Traversals without using Recursion
/* Inorder traversal with out using recursion */
int top = -1;
struct node *arr[100];
struct node
{
char data;
struct node *left;
struct node *right;
int visited;
};
static int postIndex = 6;
int search(char in[],int inStrt, int inEnd, char data);
struct node *buildTree(char in[], char pre[], int inStrt, int inEnd);
struct node* newNode(char data);
int search(char arr[], int inStrt, int inEnd, char data)
{
int i;
for(i = inStrt; i <= inEnd; i++)
{
if(arr[i] == data)
{
return i;
}
}
}
struct node *buildTree(char post[], char in[], int inStrt, int inEnd)
{
if(inStrt > inEnd)
return NULL;
// pick the last node from post-order traversal
// which happens to be the root
struct node *tNode = newNode(post[postIndex--]);
// if this node has no childern then return
if(inStrt == inEnd)
return tNode;
// find the index of this node in in-order traversal
int inIndex = search(in, inStrt, inEnd, tNode->data);
tNode->right = buildTree(post, in, inIndex+1, inEnd);
tNode->left = buildTree(post, in, inStrt, inIndex -1);
return tNode;
}
struct node* newNode(char data)
{
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = 0;
return node;
}
void push (struct node *root)
{
arr[++top] = root;
}
struct node *pop(void)
{
return arr[top--];
}
/* Inorder traversal without using recursion */
void printInorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return;
// Push all node onto the stack
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
printf("%c \t", temp->data);
temp = temp->right;
while(temp != NULL)
{
push(temp);
temp = temp->left;
}
}
printf("top inorder : %d\n", top);
}
/* Pre-order traversal without using recursion */
void printPreorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
printf("%c \t", root->data);
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
temp = temp->right;
while(temp != NULL)
{
printf("%c\t", temp->data);
push(temp);
temp= temp->left;
}
}
}
/* Post-order traversal without using recursion */
void printPostorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
push(temp);
//printf("%c %d\n", temp->data, temp->visited);
temp = temp->right;
while(temp != NULL && temp->visited == 0)
{
temp->visited = 1;
push(temp);
temp= temp->left;
}
temp = pop();
printf("%c\t", temp->data);
}
}
main()
{
char post[] = {'C', 'F', 'G', 'D', 'B', 'E', 'A'};
char in[] = {'C', 'B', 'F', 'D', 'G', 'A', 'E'};
int len = sizeof(post)/sizeof(post[0]);
int i;
struct node *root = buildTree(post, in, 0, len-1);
printf("Print the in order traversal\n");
printInorder(root);
printf("Print the pre-order traversal\n");
printPreorder(root);
printf("\nPrint the post-order traversal\n");
printPostorder(root);
}
Find the 8 digit number
Find a 8-digit number, where the first figure defines the count of zeros in this number, the second figure the count of numeral 1 in this number and so on.... Start with 8 digit number, starting from left to right, first digit indicate number of 0's in 8 digit number, second digit indicate number of 1's in 8 digit number. Similary 7th digit indicate number of 7's in 8 digit number. 70000000 //8 digit number 7 indicate number of 0's in the number. 70000001 //As number of 7's = 1 so 7th place is 1 60000001 //As due to 1 on 7th place number of zeros = 6 60000010 //As 6 is present so 7th place, number of 6's = 1; number of 7's = 0 61000010 //As 1 is present on 7th place ; number of 1's = 1 so 2nd place there should be 1 51000010 //As number of 0's = 5 51000100 //As 5 is present so 6th place is 1 number of 6's = 0; number of 7's = 0 52000100 //As number of 1's = 2 52100100 //As 2 is present on 1st place so 3rd place is 1 42100100 // As number of 0's = 4 so 1st place is 4 42101000 // As 4 is present so 5th place is 1; number of 5's, 6's and 7's = 0; We got the answer as 4210 1000.
Reverse the order of words in a string
For example: Input string is " This is my first post"
Output string will be "post first my is This";
first reverse each word.(complexity o(n))
finally reverse the whole string.(complexity O(n))
total O(n)+O(n) = O(n)
How about pushing tokens using stack and then popping all.
Number of Trailing zeros in n!
We use the fact that zeros occurs only when multiple of 5 gets multiplied to an even number. So it boils down to a problem of finding power of 5 in prime factorization of n!.
int countOfPrimeFactors(int n,int k) // This method gives count of prime factors of k for a given n in n! .
{
int count=0;
while(n>=k)
{
count+=n/k;
k= k*k;
}
return count;
}
main()
{
int n = 20;
printf("Number of zeros : %d\n", countOfPrimeFactors(n,5)); // Find prime factors of 5 in n! .
}
Construct Tree from given Inorder and Preorder traversals
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.
A
/ \
/ \
D B E F C
We recursively follow above steps and get the following tree.
A
/ \
/ \
B C
/ \ /
/ \ /
D E F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
/* program to construct tree using inorder and preorder traversals */
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
char data;
struct node* left;
struct node* right;
};
/* Prototypes for utility functions */
int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);
/* Recursive function to construct binary of size len from
Inorder traversal in[] and Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1. The function doesn't
do any error checking for cases where inorder and preorder
do not form a tree */
struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if(inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTree(in, pre, inStrt, inIndex-1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(char data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* This funtcion is here just to test buildTree() */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%c ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Driver program to test above functions */
int main()
{
char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};
int len = sizeof(in)/sizeof(in[0]);
struct node *root = buildTree(in, pre, 0, len - 1);
/* Let us test the built tree by printing Insorder traversal */
printf("\n Inorder traversal of the constructed tree is \n");
printInorder(root);
getchar();
}
Time Complexity: O(n^2). Worst case occurs when tree is left skewed. Example Preorder and Inorder traversals for worst case are {A, B, C, D} and {D, C, B, A}.
Subscribe to:
Posts (Atom)