Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present
all operations in O(1).
No memory constraint.
Init:
k=0
Insert X:
k = k+1 mod m;
A[X] = k;
B[k] = X;
Search X:
return (A[X] < m) and (B[A[X]] == X)
Delete X:
A[X] = 0;
B[k] = 0;
k = k-1;
Monday, April 11, 2011
Sunday, April 10, 2011
WAP to Calculate The Next Palindrom of Given Number Need not to be a Palindrome
#include
#include
#include
using namespace std;
//result = s + 1
void SumOne (string &s, string &result)
{
int sum, carry = 1;
for (string::reverse_iterator p = s.rbegin(); p != s.rend(); p++)
{
sum = carry + (*p - '0') ;
carry = sum / 10;
result.push_back ('0' + sum%10 );
}
if (carry) result.push_back ('1') ;
reverse (result.begin(), result.end() );
}
int main()
{
string number, left, right, revLeft ;
int tcase=0;
cin >>tcase;
int i=0;
for(i=0;i
cin >> number ;
int n = number.size();
left = n/2 > 0 ? number.substr (0, n/2) : "0" ;
right = n/2 > 0 ? number.substr ((n+1)/2, n/2): "0" ;
revLeft = left;
reverse (revLeft.begin(), revLeft.end() );
if ( revLeft.compare (right) > 0 )
{
number.replace ((n+1)/2, n/2, revLeft );
}
else
{
if ( number[(n-1)/2] != '9' )
{
number[(n-1)/2]++; //for number of even digits this modifies "left"
revLeft = number.substr (0, n/2) ;
reverse (revLeft.begin(), revLeft.end() );
number.replace ((n+1)/2, n/2, revLeft);
}
else
{
string nextSum ;
SumOne ( left, nextSum);
if ( nextSum.size() > left.size() ) { //for special pattern: "99999" or "999999"
number = "11";
number.insert (1, n-1, '0');
}
else {
if ( n % 2 ) number [(n-1)/2] = '0'; //for number like 52960
number.replace (0, nextSum.size(), nextSum);
reverse (nextSum.begin(), nextSum.end());
number.replace ( (n+1)/2, nextSum.size(), nextSum );
}
}
}
cout << number << endl;
}
return 0;
}
TC O(n)
Sc O(1)
Run Here http://ideone.com/sOkFE
#include
#include
using namespace std;
//result = s + 1
void SumOne (string &s, string &result)
{
int sum, carry = 1;
for (string::reverse_iterator p = s.rbegin(); p != s.rend(); p++)
{
sum = carry + (*p - '0') ;
carry = sum / 10;
result.push_back ('0' + sum%10 );
}
if (carry) result.push_back ('1') ;
reverse (result.begin(), result.end() );
}
int main()
{
string number, left, right, revLeft ;
int tcase=0;
cin >>tcase;
int i=0;
for(i=0;i
cin >> number ;
int n = number.size();
left = n/2 > 0 ? number.substr (0, n/2) : "0" ;
right = n/2 > 0 ? number.substr ((n+1)/2, n/2): "0" ;
revLeft = left;
reverse (revLeft.begin(), revLeft.end() );
if ( revLeft.compare (right) > 0 )
{
number.replace ((n+1)/2, n/2, revLeft );
}
else
{
if ( number[(n-1)/2] != '9' )
{
number[(n-1)/2]++; //for number of even digits this modifies "left"
revLeft = number.substr (0, n/2) ;
reverse (revLeft.begin(), revLeft.end() );
number.replace ((n+1)/2, n/2, revLeft);
}
else
{
string nextSum ;
SumOne ( left, nextSum);
if ( nextSum.size() > left.size() ) { //for special pattern: "99999" or "999999"
number = "11";
number.insert (1, n-1, '0');
}
else {
if ( n % 2 ) number [(n-1)/2] = '0'; //for number like 52960
number.replace (0, nextSum.size(), nextSum);
reverse (nextSum.begin(), nextSum.end());
number.replace ( (n+1)/2, nextSum.size(), nextSum );
}
}
}
cout << number << endl;
}
return 0;
}
TC O(n)
Sc O(1)
Run Here http://ideone.com/sOkFE
WAP to Print New Binary Tree in which each njode has sum of its left & right subtree , from Given BT
#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);
}
struct node* sumSubTree(struct node** root)
{
int LeftOld,RightOld;
struct node *l,*r;
if((*root) == NULL || ((*root) -> left== NULL && (*root)->right == NULL))
return NULL;
else
{
LeftOld = (*root)->left->data;
RightOld = (*root)->right->data;
l = sumSubTree(&(*root )->left);
r = sumSubTree(&(*root)->right);
(*root)->data = LeftOld + RightOld;
if(!l)
(*root)->data += l->data;
if(!r)
(*root)->data += r->data;
return *root;
}
}
/* 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);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root=sumSubTree(&root);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
getchar();
return 0;
}
Run Here https://ideone.com/irlOz
#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);
}
struct node* sumSubTree(struct node** root)
{
int LeftOld,RightOld;
struct node *l,*r;
if((*root) == NULL || ((*root) -> left== NULL && (*root)->right == NULL))
return NULL;
else
{
LeftOld = (*root)->left->data;
RightOld = (*root)->right->data;
l = sumSubTree(&(*root )->left);
r = sumSubTree(&(*root)->right);
(*root)->data = LeftOld + RightOld;
if(!l)
(*root)->data += l->data;
if(!r)
(*root)->data += r->data;
return *root;
}
}
/* 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);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root=sumSubTree(&root);
printf("\n Preorder traversal of binary tree is \n");
printPreorder(root);
getchar();
return 0;
}
Run Here https://ideone.com/irlOz
Wednesday, April 6, 2011
WAP to Genrate All Possible Subset of Set S..Thats The Power Set
Algorithm:
If S = (a, b, c) then the powerset(S) is the set of all subsets
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
The first "trick" is to try to define recursively.
What would be a stop state?
S = () has what powerset(S)?
How get to it?
Reduce set by one element
Consider taking an element out - in the above example, take out {c}
S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }
What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}
hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
take any element out
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS
powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
where ei is an element of S (a singleton)
Pseudo-algorithm
Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...
Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
1st using Recursion
public class PowerSet {
private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;iString str = "";
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}
}
public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; iPowerSet powerSet = new PowerSet();
System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);
}
}
}
TC O(n^2)
Sc O(n)
Run here https://ideone.com/8RuF1
2nd Iterative Method
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
#include
#include
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1< printf("%c", set[j]);
}
printf("\n");
}
}
/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);
getchar();
return 0;
}
TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG
Java program for Doing The Same
class PowerSet {
int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;iint k=i;
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);
}
counter++;
k=k>>1;
}
System.out.println();
number++;
}
}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);
}
}
Run Here https://ideone.com/LtjsT
More
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136
Powerset: A recursive algorithm
If S = (a, b, c) then the powerset(S) is the set of all subsets
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
The first "trick" is to try to define recursively.
What would be a stop state?
S = () has what powerset(S)?
How get to it?
Reduce set by one element
Consider taking an element out - in the above example, take out {c}
S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }
What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}
hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
take any element out
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS
powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
where ei is an element of S (a singleton)
Pseudo-algorithm
Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...
Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
1st using Recursion
public class PowerSet {
private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;i
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}
}
public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; i
System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);
}
}
}
TC O(n^2)
Sc O(n)
Run here https://ideone.com/8RuF1
2nd Iterative Method
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
#include
#include
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1<
}
printf("\n");
}
}
/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);
getchar();
return 0;
}
TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG
Java program for Doing The Same
class PowerSet {
int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;i
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);
}
counter++;
k=k>>1;
}
System.out.println();
number++;
}
}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);
}
}
Run Here https://ideone.com/LtjsT
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136
WAP to Genrate All Possible Subset of Set S..Thats The Power Set
Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
If S has n elements in it then P(s) will have 2^n elements
Algorithm:
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
Example:
Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111
Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc
WAP to Generate Unique Combination from Given Set ot String
What is combination and how is it different from a permutation?
The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.
"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.
For example,
For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]
From my quick Google search, I also found out
"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).
If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.
This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?
Lets get a formal definition from Wikipedia:
"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."
In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:
The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.
Some points to note about this problem.
1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.
2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm
To find the combinations of a String:
Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1
import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class StringCombinations
{
private Set combinations = new HashSet();
public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);
}
public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);
// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}
// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}
public static String readCommandLineInput(String inputMessage)
{
String inputLine ="abcd";
return inputLine;
}
public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}
}// End of StringCombinations
Run Here https://ideone.com/EPV9i
Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117
The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.
"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.
For example,
For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]
From my quick Google search, I also found out
"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).
If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.
This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?
Lets get a formal definition from Wikipedia:
"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."
In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:
The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.
Some points to note about this problem.
1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.
2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm
To find the combinations of a String:
Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1
import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class StringCombinations
{
private Set combinations = new HashSet();
public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);
}
public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);
// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}
// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}
public static String readCommandLineInput(String inputMessage)
{
String inputLine ="abcd";
return inputLine;
}
public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}
}// End of StringCombinations
Run Here https://ideone.com/EPV9i
Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117
Tuesday, April 5, 2011
There are n rocks in the river, using which the frog can leap across the river.
I saw a discussion on this question on careercup as its good question..so i pasted it here
A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4
Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths. Ofcourse there can be other arguments too.
A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4
Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.
#include
#include
#include
void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}
int main ()
{
int *array, num=4;
array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}
Run Here https://ideone.com/o00za
Solution By Tully From CareerCup
A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4
Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths. Ofcourse there can be other arguments too.
A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4
Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.
#include
#include
#include
void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}
int main ()
{
int *array, num=4;
array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}
Run Here https://ideone.com/o00za
Solution By Tully From CareerCup
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
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
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
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
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..??
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..??
Monday, April 4, 2011
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; i
}
}
}
Run Here https://ideone.com/XiWAF
Subscribe to:
Posts
(
Atom
)
