[algogeeks] SPOJ question LITE
#includeiostream
using namespace std;
struct node
{
int num;
int l,r;
node * left;
node * right;
};
node * create(node * root,int start,int end);
node * update(node * root, int i,int j);
int query(node * root,int i,int j);
main()
{
int n,q;
cinnq;
node * root=new node;
root-num=0;
root-left=NULL;
root-right=NULL;
root=create(root,0,n-1);
while(q--)
{
int type,i,j;
cintypeij;
if(type==0)
root=update(root,i,j);
if(type==1)
coutquery(root,i,j);
}
}
node * create(node * root,int start,int end)
{
if(start==end)
{
node * temp=new node();
temp-num=0;
temp-right=NULL;
temp-left=NULL;
temp-l=temp-r=start;
return temp;
}
if(start!=end)
{
if(root==NULL)
root=new node();
root-num=0;
root-l=start;
root-r=end;
root-left=create(root-left,start,(start+end)/2);
root-right=create(root-right,((start+end)/2)+1,end);
return root;
}
}
node * update(node * root,int i,int j)
{
if(root-l==root-r (root-l =iroot-r =j))
{
root-num=1-(root-num);
return root;
}
if(root-left)
root-left=update(root-left,i,j);
if(root-right)
root-right=update(root-right,i,j);
if(root-left root-right)
root-num=root-left-num+root-right-num;
return root;
}
int query(node * root,int i,int j)
{
if(root-l=i root-r=j)
return root-num;
int ans1,ans2;
if(root-left)
ans1=query(root-left,i,j);
if(root-right)
ans2=query(root-right,i,j);
if(!root-left !root-right)
return 0;
return ans1+ans2;
}
this is my solution to http://www.spoj.pl/problems/LITE/ .
But i am getting wrong answer. Can someone suggest a few test cases for
which my solution might be failing ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/h6UQhCs1W_0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Question: Reverse stack using push, pop without any auxiliary data structure
This solution works perfectly :) On Friday, June 15, 2012 10:59:22 AM UTC+5:30, Navin Kumar wrote: I corrected in function InsertAtBottom :In my code isntead of (!IsEmptyStack) use IsEmptyStack On Fri, Jun 15, 2012 at 10:49 AM, Navin Kumar algorithm.i...@gmail.comwrote: @all: In my code isntead of (!IsEmptyStack) use IsEmptyStack Logic : First pop the all element and then start putting element at bottom in reverse order i.e. the element which is fetched last is put at the bottom and so on. ex: let our stack is: 1 2 3 4 (1 is at bottom). function Call is will be: Reverse(S) --Reverse(S) --Reverse(S) --Reverse(S) --stack empty so return InsertAtBottom(4) InsertAtBottom(3)InsertAtBottom(2) InsertAtBottom(1) going back First 1 will be placed at bottom: stack content :1 now 2 will be placed at bottom: stack content will be: 2 1 now 3 will be placed at bottom: stack content will be: 3 2 1 now 4 will be placed at bottom: stack content will be:4 3 2 1 On Thu, Jun 14, 2012 at 2:46 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: stack means inbuild stack we cant use any DS from our program explicitly. On Thu, Jun 14, 2012 at 2:44 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: to store items in stack you will need some DS. Do they mean you cant use any auxillary DS than stack ? On Thu, Jun 14, 2012 at 2:24 PM, Ashish Goel ashg...@gmail.com wrote: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pcs-ebKU_t8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Directi Question
@maddy: The students should be assigned consecutive books only. That is, u
CANNOT assign book 1, 2 and 5 to a single student. either assign book 1, 2
and 3 or 1 and 2 or any such combination of consecutive numbers.
On Thursday, June 14, 2012 12:26:09 PM UTC+5:30, algogeek wrote:
In a library there are N books with the number of pages in i th book given
by bi . These books are to be distributed among K students such that the
difference between the largest sum of pages in the books assigned to any
student and the smallest sum of number of pages in the books assigned to
any student is minimum for the given input. Also the books are arranged in
a certain order and this order must never be changed.
For eg:
suppose B[ ] contains the number of pages in each book.
then
N=6
K=3
B={3,7,8,2,6,4}
then the output will be 0 as we can give book 1 and 2 to student 1 and
book 3 and 4 to student 2 and the remaining to student 3. That makes 10
pages for student 1 10 for 2 and 10 for 3 and thus the difference is 0
similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/7jAw-C4JI1AJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Interview Question
could u explain how would you use a trie for this?? On Thursday, June 14, 2012 1:01:00 PM UTC+5:30, Mohit Rathi wrote: Hi, *There are two arrays of length 100 each. Each of these has initially n (n=100) elements. First array contains names and the second array contains numbers such that ith name in array1 corresponds to ith number in array2. Write a program which asks the user to enter a name, finds it in array1,* *a. if it exists, then print the corresponding number in array2, b. else ask the user to input its associated number and add the number and name to array2 and array1 respectively, and update the size of list* I can think of solving it through linear walk to the array. Anyone with more optimized algorithm like BST or HashTable? comments are welcome Thanks -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-BW4cpALLgIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Directi Question
In a library there are N books with the number of pages in i th book given
by bi . These books are to be distributed among K students such that the
difference between the largest sum of pages in the books assigned to any
student and the smallest sum of number of pages in the books assigned to
any student is minimum for the given input. Also the books are arranged in
a certain order and this order must never be changed.
For eg:
suppose B[ ] contains the number of pages in each book.
then
N=6
K=3
B={3,7,8,2,6,4}
then the output will be 0 as we can give book 1 and 2 to student 1 and book
3 and 4 to student 2 and the remaining to student 3. That makes 10 pages
for student 1 10 for 2 and 10 for 3 and thus the difference is 0
similarly if B={3,6,8,2,6,4} then the minimum difference will be 1 .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/JjKITS_gN9UJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Permutations of a string
Johnson trotter algorithm is another way to generate all permutations..
On Saturday, May 5, 2012 4:08:13 PM UTC+5:30, Sairam wrote:
I have written a code which gives all permutations of a string. I have
assumed that all the characters in a given string are distinct.
The main idea is as follows
-if suppose abc is given first
my base case is to form permutations of two characters
so I will have ab and ba
Now, I will just switch places of c - like cab,acb and abc - from
the string ab
Similarly obtain cba,bca and bac from ba.
I have implemented this logic using recursion. The implementation is given
below
I would like to know is there is any other efficient ways to do this
#includeiostream
#includestring
#includestring.h
#define SIZE 7
using namespace std;
string * permutations (char *array,string *stringarray,int len);
string * Join(string *stringarray,char append);
int factorial (int n);
int numpermutations;
main()
{
char array[]=bcad;
//Write a program to find the factorial of a number
numpermutations = factorial(strlen(array));
string *stringarray = new string[numpermutations];
int i;
for(i=0;inumpermutations;i++)
stringarray[i] = \0;
permutations(array,stringarray,strlen(array)-1);
i=0;
while(i!=numpermutations)
{
coutstringarray[i]endl;
i++;
}
}
int factorial (int n)
{
int fact;
if(n==2)
return 2;
else
{
fact = n*factorial(n-1);
return fact;
}
}
string *permutations(char *array,string *stringarray, int len)
{
string * tempstring;
if(len == 1)
{
char temp[3];
temp[0] = array[0];//Here I am doing the swapping
temp[1] = array[1];
temp[2] = '\0';
stringarray[0] = temp;
temp[0] = array[1];
temp[1] = array[0];
temp[2] = '\0';
stringarray[1] = temp;
int i;
}
else
{
stringarray =
Join(permutations(array,stringarray,len-1),array[len]);//using recursion
}
return stringarray;
}
string * Join(string *stringarray,char append)//This is to join string
and a character
{
int str_len = stringarray[0].length();//Get the length of one of the
strings
string tempstring[numpermutations];
int i;
for(i=0;inumpermutations;i++)
tempstring[i] = \0;
int j,temparrayindex=0;
i=0;
/*coutFirst print wht is string arraystringarray[0]endl;
coutstringarray[1]stringarray[1]endl;*/
while(stringarray[i]!=\0)
{
char *temp = new char[str_len+1];
for(j=0;j=str_len;j++)
{
int k;
for(k=0;kj;k++)
temp[k] = stringarray[i][k];
temp[k] = append;
for(k=j+1;k=str_len;k++)
temp[k] = stringarray[i][k-1];
temp[k]='\0';
tempstring[temparrayindex]=temp;
temparrayindex++;
}
delete []temp;
i++;
}
i=0;
while(i != numpermutations)
{
stringarray[i] = tempstring[i];
i++;
}
return stringarray;
}
On Saturday, May 5, 2012 4:08:13 PM UTC+5:30, Sairam wrote:
I have written a code which gives all permutations of a string. I have
assumed that all the characters in a given string are distinct.
The main idea is as follows
-if suppose abc is given first
my base case is to form permutations of two characters
so I will have ab and ba
Now, I will just switch places of c - like cab,acb and abc - from
the string ab
Similarly obtain cba,bca and bac from ba.
I have implemented this logic using recursion. The implementation is given
below
I would like to know is there is any other efficient ways to do this
#includeiostream
#includestring
#includestring.h
#define SIZE 7
using namespace std;
string * permutations (char *array,string *stringarray,int len);
string * Join(string *stringarray,char append);
int factorial (int n);
int numpermutations;
main()
{
char array[]=bcad;
//Write a program to find the factorial of a number
numpermutations = factorial(strlen(array));
string *stringarray = new string[numpermutations];
int i;
for(i=0;inumpermutations;i++)
stringarray[i] = \0;
permutations(array,stringarray,strlen(array)-1);
i=0;
while(i!=numpermutations)
{
coutstringarray[i]endl;
i++;
}
}
int factorial (int n)
{
int fact;
if(n==2)
return 2;
else
{
fact = n*factorial(n-1);
return fact;
}
}
string *permutations(char *array,string *stringarray, int len)
{
string * tempstring;
if(len == 1)
[algogeeks] symmetric binary tree
How to check if a given binary tree is structurally symmetric ie. the left sub tree should be mirror image of right sub tree and vice-versa. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
