Re: [algogeeks] Re: Amazon: sort array
I think this will work.
# include stdio.h
void my_print(int *,int);
void swap(int a , intb)
{
a = a + b;
b = a - b;
a = a - b;
}
void sort(int* array, int SIZE, int i, int j)
{
while(ij)
{
my_print(array,SIZE);
if(array[i] = array[j])
i++;
if(array[j] array[i])
{
swap(array[i] , array[j]);
i++;
int temp = j;
while(temp (SIZE-1) (array[temp] array[temp+1]) )
{
swap(array[temp] , array[temp + 1]);
temp++;
}
}
}
}
void my_print(int * array, int SIZE)
{
printf(\n);
int i = 0;
for(; i SIZE ; i++)
printf(%d, ,array[i]);
printf(\n);
}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
int array3[10] = {10,20,30,40,50,23,27,40};
//sort(array1,8,0,4);
//sort(array2,10,0,6);
sort(array3,8,0,5);
//my_print(array1,8);
//my_print(array2,10);
my_print(array3,8);
return 0;
}
On Mon, Jul 12, 2010 at 10:20 AM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
@souravsain
for input {10,20,30,40,50,23,27};
ur output is coming 10, 20, 23, 27, 40, 30, 50,
which not SORTED array.
On Jul 10, 6:19 pm, souravsain souravs...@gmail.com wrote:
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look athttp://codepad.org/iMBTwAL7
Appriciate the effort taken by you to analyze the solution and do let
me know if you still do not agree with the code.
Regards,
Sourav
On Jul 8, 9:03 pm, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1
for
further comparison
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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: sort array
Is not ur code is running in o(n^2) complexity
You have used two while loop ...
plzz eleborate if i m wrong .
On Jul 12, 11:00 am, Amit Mittal amit.mitt...@gmail.com wrote:
I think this will work.
# include stdio.h
void my_print(int *,int);
void swap(int a , intb)
{
a = a + b;
b = a - b;
a = a - b;}
void sort(int* array, int SIZE, int i, int j)
{
while(ij)
{
my_print(array,SIZE);
if(array[i] = array[j])
i++;
if(array[j] array[i])
{
swap(array[i] , array[j]);
i++;
int temp = j;
while(temp (SIZE-1) (array[temp] array[temp+1])
)
{
swap(array[temp] , array[temp + 1]);
temp++;
}
}
}
}
void my_print(int * array, int SIZE)
{
printf(\n);
int i = 0;
for(; i SIZE ; i++)
printf(%d, ,array[i]);
printf(\n);}
int main()
{
int array1[8] = {1,3,6,7,4,5,6,8};
int array2[10] = {1,2,3,5,6,7,4,8,9,10};
int array3[10] = {10,20,30,40,50,23,27,40};
//sort(array1,8,0,4);
//sort(array2,10,0,6);
sort(array3,8,0,5);
//my_print(array1,8);
//my_print(array2,10);
my_print(array3,8);
return 0;
}
On Mon, Jul 12, 2010 at 10:20 AM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
@souravsain
for input {10,20,30,40,50,23,27};
ur output is coming 10, 20, 23, 27, 40, 30, 50,
which not SORTED array.
On Jul 10, 6:19 pm, souravsain souravs...@gmail.com wrote:
@Jitendra
I have run the code with input given by you and found that it works
well.
Please have a look athttp://codepad.org/iMBTwAL7
Appriciate the effort taken by you to analyze the solution and do let
me know if you still do not agree with the code.
Regards,
Sourav
On Jul 8, 9:03 pm, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@souravsain
Consider your algo for the case
int arr[] = {10,20,30,40,50,23,27};
everytime when you increment the j you are missing on element i.e j-1
for
further comparison
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] sort in O(n)
if we have 1 2 5 7 3 4 6 can you explain how to do in place merge... the elements are in an array ? On Sun, Jul 11, 2010 at 10:29 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: its easy suppose the array is 12345 4321 2345 4321 it increases then dcreases then increases and decreases again first of all in a single scan find the location of decreasing sub-arrays here it is 5 to 8 and 13-16 and reverse the decreasing array. so the array becomes 12345 1234 2345 1234 now do simple inplace merging of sorted arrays. On Sun, Jul 11, 2010 at 9:08 PM, srikanth sg srikanthini...@gmail.comwrote: thr is no search option there .. if u can gimme the link that will be good .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] partition a number
Partitioning a given integer n into unique partitions of size m. like if n=10,m=4, 7111 is one such partition. Give all such partitions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Difference b/w two elements in a array
traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: There are 2 type of values - 1 byte and 2 byte given a pointer to any point in the string tell me if its a 1B or 2B value ending there. MSB of 1-byte character is 0 and MSB of 2-byte
is it something different than this
foo(char *p, int num)
{
if(!p) return error
if(num 0 p[num-1] == 0) print 2 byte value
else
print 1 byte value
}
On Jul 11, 11:18 pm, Tech Id tech.login@gmail.com wrote:
Question is not clear to me :(
Can you explain a little more and also give an example if possible?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: Difference b/w two elements in a array
traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Difference b/w two elements in a array
2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] Re: Difference b/w two elements in a array
order nlogn is trivial .. any thing better ?? On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg srikanthini...@gmail.comwrote: 2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: amazon:-
edit distance.. On Mon, Jul 12, 2010 at 10:22 AM, Anil Kumar S. R. sra...@gmail.com wrote: Use the A* Search approach, which is based on a function f(x) = g(x) + h(x), where f(x) is the total cost, g(x) is the cost to travel to the current node and h(x) is the heuristic estimate of the cost remaining to the goal, from the current node. Use the hamming distance approach to find h(x), which specifies how much two words differ. Use the data structures such as hash table and min priority queue to compute f(x). Anil Kumar S. R. The best way to succeed in this world is to act on the advice you give to others. On 11 July 2010 08:21, sharad kumar sharad20073...@gmail.com wrote: @jalaj how u make graph so that we can apply dijkasta algo plz xpalain -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] xoring
i can give an idea..
start from the LHS bit.. ( for 3 =*0*101)
divide all numbers in two groups A0and A1 , A1 = 1XXX, A0 = 0XXX form
we know that an element in A1 xor an element in A0 will give the soln for
this..
IF either of set is empty then we have to go further like this way
now divide A1 = A10 and A11 such that A11 = 11XX and A10 =10XX
and so on..
now XOR of the elements from group A11 and A10 is max or A01 and A00 etc
this way we can do it..
on each stage i am eleminating some elements..
On Mon, Jul 12, 2010 at 12:50 AM, sharad kumar sharad20073...@gmail.comwrote:
given a set of numbers
u hve to find the pair which give maximum value if we xor that pair
ex a={1,3,6,7,8,9}
then ans is 15 as 7 xor 8
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Minimum Window String
i think ques is not complete.. otherwise above ans is rite.. i suppose.. On Mon, Jul 12, 2010 at 10:00 AM, Anand anandut2...@gmail.com wrote: you can use longest common subsequence algorithm to solve it. http://codepad.org/NDAeIpxR On Sun, Jul 11, 2010 at 9:32 AM, amit amitjaspal...@gmail.com wrote: Given a set T of characters and a string S , find the minimum window in S which will contain all the characters in T in complexity O(n) . Constraint : The characters may appear in any order -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Difference b/w two elements in a array
you can find both the smallest and the second smallest number ... Anil On Mon, Jul 12, 2010 at 3:21 PM, ankur aggarwal ankur.mast@gmail.comwrote: order nlogn is trivial .. any thing better ?? On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg srikanthini...@gmail.comwrote: 2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] Re: Difference b/w two elements in a array
oh never mind that was wrong... :P Anil On Mon, Jul 12, 2010 at 5:03 PM, Anil C R cr.a...@gmail.com wrote: you can find both the smallest and the second smallest number ... Anil On Mon, Jul 12, 2010 at 3:21 PM, ankur aggarwal ankur.mast@gmail.comwrote: order nlogn is trivial .. any thing better ?? On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg srikanthini...@gmail.comwrote: 2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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: Histogram Problem
You will need width of each bar too perhaps. Why should this need any algo? Just get the one which has maximum height or if width is also given then the one with maximum height x width It is O(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: sort in O(n)
This is a good solution. Reversing the arrays will be O(n) Then merging will be O(n) too. In place merge is something like this. Have two indices as start1 and start2 start1 points to beginning of mini-sorted portion1 start2 points to beginning of mini-sorted portion2 Increase both start1 and start2 and swap when necessary. adjust start1 and start2 accordingly. Do the same for other mini-sorted arrays. So the complexity of this is mO(n) where m is the number of mini arrays. For m=1, it becomes O(n^2) as expected for a normal sort! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: partition a number
This can be done by recursion. Each number can be represented as: N = 1) (N-1), 1 2) (N-2), 2 3) (N-3), 3 N) (1), (N-1) For each number (N-k), repeat the above in recursion. = Gives all the unique partitions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Mainframe Developer
send your matching profiles to *...@dwlabs.com * Hello, We have this immediate need with our direct client in Tampa, please let me know if you have any suitable candidates. *Req: Mainframe Developer (Telecom industry experience is a huge plus)* Skills:* Mainframe, **Sync Sort**, JCL, TSO* * * Location: Tampa, FL Duration: 6-12 months contract Rate: $35/hr C-C -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: sort in O(n)
@ above can u please be more specific let A[1,9,10] and B [2,4,6] Now how to swap so that the complexity remains O(n) -- Forwarded message -- From: Tech Id tech.login@gmail.com Date: Mon, Jul 12, 2010 at 8:18 PM Subject: [algogeeks] Re: sort in O(n) To: Algorithm Geeks algogeeks@googlegroups.com This is a good solution. Reversing the arrays will be O(n) Then merging will be O(n) too. In place merge is something like this. Have two indices as start1 and start2 start1 points to beginning of mini-sorted portion1 start2 points to beginning of mini-sorted portion2 Increase both start1 and start2 and swap when necessary. adjust start1 and start2 accordingly. Do the same for other mini-sorted arrays. So the complexity of this is mO(n) where m is the number of mini arrays. For m=1, it becomes O(n^2) as expected for a normal sort! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Pattern Matching
Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. fort example find if a*b*cd*, or *win or *def* exists in the text. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Minimum Window String
@ above Consider S=anand T={'d','n'.'a'}
LCS is na but the Answer is and . Here the order of characters don't
matter as i have mentioned .
One way is you can take LCS with every possible permutation of T but that
would be exponential
On Mon, Jul 12, 2010 at 3:23 PM, ankur aggarwal ankur.mast@gmail.comwrote:
i think ques is not complete..
otherwise above ans is rite.. i suppose..
On Mon, Jul 12, 2010 at 10:00 AM, Anand anandut2...@gmail.com wrote:
you can use longest common subsequence algorithm to solve it.
http://codepad.org/NDAeIpxR
On Sun, Jul 11, 2010 at 9:32 AM, amit amitjaspal...@gmail.com wrote:
Given a set T of characters and a string S , find the minimum window
in S which will contain all the characters in T in complexity O(n) .
Constraint : The characters may appear in any order
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: xoring
I am not sure if the above is very clear. Ankur, if you can explain it some more, it would be really great. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] graph
1.Give an efficient algorithm which takes as input a directed graph G = (V,E), and determines whether or not there is a vertex s is in V from which all other vertices are reachable.? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] graph
Give a linear-time algorithm for the following task. Input: : A directed acyclic graph G (V,E) Question: Does G contain a directed path that touches every vertex exactly once? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Minimum Window String
@amit: In this case, we can calculate the length of string S and T and
reverse the string whose length is smaller than the other. Then Take LCS of
it. To get the final answer.
On Mon, Jul 12, 2010 at 7:05 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above Consider S=anand T={'d','n'.'a'}
LCS is na but the Answer is and . Here the order of characters don't
matter as i have mentioned .
One way is you can take LCS with every possible permutation of T but that
would be exponential
On Mon, Jul 12, 2010 at 3:23 PM, ankur aggarwal
ankur.mast@gmail.comwrote:
i think ques is not complete..
otherwise above ans is rite.. i suppose..
On Mon, Jul 12, 2010 at 10:00 AM, Anand anandut2...@gmail.com wrote:
you can use longest common subsequence algorithm to solve it.
http://codepad.org/NDAeIpxR
On Sun, Jul 11, 2010 at 9:32 AM, amit amitjaspal...@gmail.com wrote:
Given a set T of characters and a string S , find the minimum window
in S which will contain all the characters in T in complexity O(n) .
Constraint : The characters may appear in any order
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] graph
topological sort would cover every vertex once. The path given by Topological sort would be the answer. We can also calculate the vertices given by topological sort and compare it with given vertices. if it is same then graph G does contain a directed path that touches every vertex exactly once. On Mon, Jul 12, 2010 at 10:08 AM, Love-143 lovekesh6mn...@gmail.com wrote: Give a linear-time algorithm for the following task. Input: : A directed acyclic graph G (V,E) Question: Does G contain a directed path that touches every vertex exactly once? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] 32 comparisons only
How will you search an integer in just 32 comparisons in an unsorted group of integers? Devise a data structure for it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: sort in O(n)
@amit: according to your given example this how the logic works.
In the below code I took an array a[]={1,9,10,2,4,6}; in the example at the
mid point second array start so mid point logic works here. but according to
given question we can scan through the array once and can find out where
actually the array start decreasing which is starting point of the second
array.
Complexity of merge the array is O(n).
http://codepad.org/PCoswp0c
On Mon, Jul 12, 2010 at 8:06 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above can u please be more specific
let A[1,9,10] and B [2,4,6]
Now how to swap so that the complexity remains O(n)
-- Forwarded message --
From: Tech Id tech.login@gmail.com
Date: Mon, Jul 12, 2010 at 8:18 PM
Subject: [algogeeks] Re: sort in O(n)
To: Algorithm Geeks algogeeks@googlegroups.com
This is a good solution.
Reversing the arrays will be O(n)
Then merging will be O(n) too.
In place merge is something like this.
Have two indices as start1 and start2
start1 points to beginning of mini-sorted portion1
start2 points to beginning of mini-sorted portion2
Increase both start1 and start2 and swap when necessary.
adjust start1 and start2 accordingly.
Do the same for other mini-sorted arrays.
So the complexity of this is mO(n) where m is the number of mini
arrays.
For m=1, it becomes O(n^2) as expected for a normal sort!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] Re: sort in O(n)
u are using extra memory which is not supposed to be done..
On Mon, Jul 12, 2010 at 10:56 AM, Anand anandut2...@gmail.com wrote:
@amit: according to your given example this how the logic works.
In the below code I took an array a[]={1,9,10,2,4,6}; in the example at the
mid point second array start so mid point logic works here. but according to
given question we can scan through the array once and can find out where
actually the array start decreasing which is starting point of the second
array.
Complexity of merge the array is O(n).
http://codepad.org/PCoswp0c
On Mon, Jul 12, 2010 at 8:06 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above can u please be more specific
let A[1,9,10] and B [2,4,6]
Now how to swap so that the complexity remains O(n)
-- Forwarded message --
From: Tech Id tech.login@gmail.com
Date: Mon, Jul 12, 2010 at 8:18 PM
Subject: [algogeeks] Re: sort in O(n)
To: Algorithm Geeks algogeeks@googlegroups.com
This is a good solution.
Reversing the arrays will be O(n)
Then merging will be O(n) too.
In place merge is something like this.
Have two indices as start1 and start2
start1 points to beginning of mini-sorted portion1
start2 points to beginning of mini-sorted portion2
Increase both start1 and start2 and swap when necessary.
adjust start1 and start2 accordingly.
Do the same for other mini-sorted arrays.
So the complexity of this is mO(n) where m is the number of mini
arrays.
For m=1, it becomes O(n^2) as expected for a normal sort!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] Re: sort in O(n)
In case if you need in place merging than you need to use bi- tonic merge.
But the only condition is total array length should be power of two.
http://codepad.org/hG8CnM1l
On Mon, Jul 12, 2010 at 11:13 AM, srikanth sg srikanthini...@gmail.comwrote:
u are using extra memory which is not supposed to be done..
On Mon, Jul 12, 2010 at 10:56 AM, Anand anandut2...@gmail.com wrote:
@amit: according to your given example this how the logic works.
In the below code I took an array a[]={1,9,10,2,4,6}; in the example at
the mid point second array start so mid point logic works here. but
according to given question we can scan through the array once and can find
out where actually the array start decreasing which is starting point of the
second array.
Complexity of merge the array is O(n).
http://codepad.org/PCoswp0c
On Mon, Jul 12, 2010 at 8:06 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above can u please be more specific
let A[1,9,10] and B [2,4,6]
Now how to swap so that the complexity remains O(n)
-- Forwarded message --
From: Tech Id tech.login@gmail.com
Date: Mon, Jul 12, 2010 at 8:18 PM
Subject: [algogeeks] Re: sort in O(n)
To: Algorithm Geeks algogeeks@googlegroups.com
This is a good solution.
Reversing the arrays will be O(n)
Then merging will be O(n) too.
In place merge is something like this.
Have two indices as start1 and start2
start1 points to beginning of mini-sorted portion1
start2 points to beginning of mini-sorted portion2
Increase both start1 and start2 and swap when necessary.
adjust start1 and start2 accordingly.
Do the same for other mini-sorted arrays.
So the complexity of this is mO(n) where m is the number of mini
arrays.
For m=1, it becomes O(n^2) as expected for a normal sort!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] algorithm to draw a line
2 coordinate points p(x,y)and q(x,y) are given and write an algorithm to draw aline -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] algorithm to draw a line
draw a line or equation of a line? On Mon, Jul 12, 2010 at 4:38 PM, Anand anandut2...@gmail.com wrote: 2 coordinate points p(x,y)and q(x,y) are given and write an algorithm to draw aline -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] graph
@anand ..can you explain it more with example On Mon, Jul 12, 2010 at 10:19 AM, Anand anandut2...@gmail.com wrote: topological sort would cover every vertex once. The path given by Topological sort would be the answer. We can also calculate the vertices given by topological sort and compare it with given vertices. if it is same then graph G does contain a directed path that touches every vertex exactly once. On Mon, Jul 12, 2010 at 10:08 AM, Love-143 lovekesh6mn...@gmail.comwrote: Give a linear-time algorithm for the following task. Input: : A directed acyclic graph G (V,E) Question: Does G contain a directed path that touches every vertex exactly once? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] 2_D matrix
@jalaj: sorry for delay i was busy these days
the implementation of my method is a bit hard because R2 and R4 which i
mentioned before are not always squares
and in that case we must first break the rectangles into squares and then
perform the search on squares
here breakToSquares function breaks a rectangle to min number of squares and
returns true if x was in one of them
bool rec(int x,int sti,int stj,int n,int m){
//x is what we're searching for. sti and stj show the starting point of the
matrix. m and n show the size
if (m==1 n==1){
if (a[sti][stj]==x)
return true;
else
return false;
}
if (m==0 || n==0)
return false;
if (n!=m)
return breakToSquares(x,sti,stj,m,n);
firsti=sti;
firstj=stj;
lasti=sti+n;
lastj=stj+m;
while (firstilasti firstjlastj){ // binsearch loop
i=(firsti+lasti)/2;
j=(firstj+lastj)/2;
if (a[i][j]==x)
return true;
if (a[i][j]x a[i+1][j+1]x)
break;
if (a[i+1][j+1]x){
firsti=i+1;
firstj=j+1;
}
if (xa[i][j]){
lasti=i;
lastj=j;
}
}
if (rec(i,stj,n-i,j+1) || rec(sti,j,i+1,m-j))
return true;
return false;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Minimum Window String
@ anand I think u did'nt get the point
what if T=['n' , 'n', 'a']
then if u reverse u wont get any LCS but answer is nan . Plz try to get
the jist of the question.
On Mon, Jul 12, 2010 at 10:44 PM, Anand anandut2...@gmail.com wrote:
@amit: In this case, we can calculate the length of string S and T and
reverse the string whose length is smaller than the other. Then Take LCS of
it. To get the final answer.
On Mon, Jul 12, 2010 at 7:05 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above Consider S=anand T={'d','n'.'a'}
LCS is na but the Answer is and . Here the order of characters don't
matter as i have mentioned .
One way is you can take LCS with every possible permutation of T but that
would be exponential
On Mon, Jul 12, 2010 at 3:23 PM, ankur aggarwal ankur.mast@gmail.com
wrote:
i think ques is not complete..
otherwise above ans is rite.. i suppose..
On Mon, Jul 12, 2010 at 10:00 AM, Anand anandut2...@gmail.com wrote:
you can use longest common subsequence algorithm to solve it.
http://codepad.org/NDAeIpxR
On Sun, Jul 11, 2010 at 9:32 AM, amit amitjaspal...@gmail.com wrote:
Given a set T of characters and a string S , find the minimum window
in S which will contain all the characters in T in complexity O(n) .
Constraint : The characters may appear in any order
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Dynamic Programming Problem on Strings
dp[i][j] is the number of strings that have i As and j Bs dp[0][0]=1; // s= for (i=1;i=n/2;i++) dp[i][0]=1; // s=AAA... for (i=1;i=n/2;i++) dp[0][i]=0; // the 2nd constraint for (i=1;i=n/2;i++) for (j=1;j=n/2;j++) if (ji) dp[i][j]=0; // the 2nd constraint else dp[i][j]=dp[i-1][j]+dp[i][j-1]; dp[n/2][n/2] would be the result -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] 32 comparisons only
make a bitwise trie since the height would be 32 (number of bits in an integer) u only need 32 comparisons to find an element -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Difference b/w two elements in a array
This problem cannot be solved in less than O(nlgn) time with O(1) space. The Element Distinctness Problem has a proven lower bound of Omega(nlgn). If the least difference problem could be solved in O(n) then we can reduce the ED Problem to Least Difference problem and solve it in O(n) time. This contradicts the lower bound. http://en.wikipedia.org/wiki/Element_distinctness_problem We can use extra space do counting sort but even that will not be O(size of array) but actually O(max value in the array). On Jul 12, 5:51 am, ankur aggarwal ankur.mast@gmail.com wrote: order nlogn is trivial .. any thing better ?? On Mon, Jul 12, 2010 at 2:51 PM, srikanth sg srikanthini...@gmail.comwrote: 2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] graph
your 1st Q: for each vertex run a dfs and count the number of vertices it can reach O( V^2 + VE ) another solution would be using an algorithm similar to floyd-warshal O(V^3) a[src][dest] is true if there is an edge src-dest for (k=0;kn;k++) for (i=0;in;i++) for (j=0;jn;j++) if (a[i][k] a[k][j]) a[i][k]=true; now a[src][dest] is true if there is path from src to dest now we just need to count the number of reachable vertices for each vertex your 2nd Q: Anand is right! :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Phone Numbers Yet Again!!!
this can be done in O(n) using DP:
for (i=n-1;i=0;i--){
dp[i]=max(dp[i+2],dp[i+3]); // usual
if (a[i]==a[i+1]) // excellent size 2
dp[i]=max(dp[i],2+dp[i+2]);
if (a[i]==a[i+1] a[i+1]==a[i+2])//excellent size 3
dp[i]=max(dp[i],2+dp[i+3]);
if (a[i]==a[i+1] || a[i]==a[i+2] || a[i+1]==a[i+2]) // good
dp[i]=max(dp[i],1+dp[i+3]);
}
the result is in dp[0]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Re: sort in O(n)
@abv amit askd inplace merging
On Mon, Jul 12, 2010 at 11:26 PM, Anand anandut2...@gmail.com wrote:
@amit: according to your given example this how the logic works.
In the below code I took an array a[]={1,9,10,2,4,6}; in the example at the
mid point second array start so mid point logic works here. but according to
given question we can scan through the array once and can find out where
actually the array start decreasing which is starting point of the second
array.
Complexity of merge the array is O(n).
http://codepad.org/PCoswp0c
On Mon, Jul 12, 2010 at 8:06 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
@ above can u please be more specific
let A[1,9,10] and B [2,4,6]
Now how to swap so that the complexity remains O(n)
-- Forwarded message --
From: Tech Id tech.login@gmail.com
Date: Mon, Jul 12, 2010 at 8:18 PM
Subject: [algogeeks] Re: sort in O(n)
To: Algorithm Geeks algogeeks@googlegroups.com
This is a good solution.
Reversing the arrays will be O(n)
Then merging will be O(n) too.
In place merge is something like this.
Have two indices as start1 and start2
start1 points to beginning of mini-sorted portion1
start2 points to beginning of mini-sorted portion2
Increase both start1 and start2 and swap when necessary.
adjust start1 and start2 accordingly.
Do the same for other mini-sorted arrays.
So the complexity of this is mO(n) where m is the number of mini
arrays.
For m=1, it becomes O(n^2) as expected for a normal sort!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT IIIT- Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] algorithm to draw a line
Algorithm to draw a line. While searching on net, I got few pointers. http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html On Mon, Jul 12, 2010 at 4:53 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: draw a line or equation of a line? On Mon, Jul 12, 2010 at 4:38 PM, Anand anandut2...@gmail.com wrote: 2 coordinate points p(x,y)and q(x,y) are given and write an algorithm to draw aline -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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] Phone Numbers Yet Again!!!
@amit..can you little explain this
On Mon, Jul 12, 2010 at 4:50 PM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
this can be done in O(n) using DP:
for (i=n-1;i=0;i--){
dp[i]=max(dp[i+2],dp[i+3]); // usual
if (a[i]==a[i+1]) // excellent size 2
dp[i]=max(dp[i],2+dp[i+2]);
if (a[i]==a[i+1] a[i+1]==a[i+2])//excellent size 3
dp[i]=max(dp[i],2+dp[i+3]);
if (a[i]==a[i+1] || a[i]==a[i+2] || a[i+1]==a[i+2]) // good
dp[i]=max(dp[i],1+dp[i+3]);
}
the result is in dp[0]
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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: sort in O(n)
On Jul 12, 10:48 am, Tech Id tech.login@gmail.com wrote: This is a good solution. Reversing the arrays will be O(n) Then merging will be O(n) too. In place merge is something like this. Have two indices as start1 and start2 start1 points to beginning of mini-sorted portion1 start2 points to beginning of mini-sorted portion2 Increase both start1 and start2 and swap when necessary. adjust start1 and start2 accordingly. Do the same for other mini-sorted arrays. So the complexity of this is mO(n) where m is the number of mini arrays. For m=1, it becomes O(n^2) as expected for a normal sort! Correct algorithms for in-place merge are much harder than what you're describing here. Think it through carefully, and you'll see this. And don't forget that if you are merging K lists, you need at least K log K comparisons to decide the merge order at each step. So if the lists being merged have about N items each, the cost of merging is O(N K log K) . In other words, the K in K-tonic makes a difference. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Phone Numbers Yet Again!!!
@ashish: i think u meant amir! anyway... profit for an excellent group is 2 and for a good group it's 1 dp[i] is the max profit for memorizing a[i], a[i+1], ... , a[n] dp is initialized to 0 so for example if a[i]==a[i+1]==a[i+2] it means that we can group a[i] a[i+1] a[i+2] together in an excellent group (+2 profit) so dp[i+3]+2 can be a better answer for dp[i] the rest of the for loop is just checking these cases i hope it's clear now -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Minimum Window String
suppose n is the size of S and m is the size of T
make to pointers p1=0 and p2=0
make another array C[]={0,0,...} which c[i] counts the number
of occurrence of T[i] in S[p1],S[p1+1]...S[p2]
n1=0 is the number of nonzero elements in C so each time n1==m means that
range p1..p2 can be an answer
first increase p2 (and C[i]s if necessary) until n1==m so if p2==n and n1m
then there is no such subsequence
now increase p1 until still n1==m
now each time try to add a new element from S (S[p2+1])
and see if we can increase p1 which means decreasing C[S[p1]] doesn't make
it 0
continue until p2==n
min(p2-p1+1) in every step will yield the result
(this algo doesn't work fine if we have duplicates in T)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: algorithm to draw a line
See en.wikipedia.org/wiki/Bresenham's_line_algorithm Dave On Jul 12, 7:38 pm, Anand anandut2...@gmail.com wrote: 2 coordinate points p(x,y)and q(x,y) are given and write an algorithm to draw aline -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Remove Extra Parenthesis
On Jul 11, 9:58 am, amit amitjaspal...@gmail.com wrote:
Give a algorithm to remove extra pair of parenthesis
Remove unnecessary from an expression :
1) (((a))) = a
2) (a+b) = a+b
3) (a+b)*c = (a+b)*c
4)(((a+b)*(c+d))+e) = (a+b)*(c+d)+e
We can build an abstract syntax tree with a simple parser and then
walk the tree to print out the expression with only the parentheses
that are really needed. If we assume both + and * are associative,
this is very easy: The only case where we need parens is when a +
occurs as either the left or right child of a *.
The problem gets more interesting with - and / because e.g. although
1+2+3 = 1+(2+3), it is not true that 1-2-3 = 1-(2-3). I'll leave this
to you.
So here you go:
#include stdio.h
#include stdlib.h
// Current character.
int ch;
// Very simple scanner.
#define SCAN do ch = getchar(); while (ch == ' ')
// Abstract syntax tree node.
typedef struct node_s {
int op;
struct node_s *lhs, *rhs;
} NODE;
// Allocate a new node.
NODE *new(int op, NODE *lhs, NODE *rhs)
{
NODE *r = malloc(sizeof *r);
r-op = op; r-lhs = lhs; r-rhs = rhs;
return r;
}
// Simple recursive descent parser builds syntax tree.
NODE *expr(void);
NODE *term(void);
NODE *factor(void);
NODE *line(void)
{
NODE *r = expr();
if (ch != '\n') {
fprintf(stderr, junk after expr\n);
exit(1);
}
return r;
}
NODE *expr(void)
{
NODE *r = term();
while (ch == '+') {
SCAN;
r = new('+', r, term());
}
return r;
}
NODE *term(void)
{
NODE *r = factor();
while (ch == '*') {
SCAN;
r = new('*', r, factor());
}
return r;
}
NODE *factor(void)
{
NODE *r = 0;
if (ch == '(') {
SCAN;
r = expr();
if (ch != ')') {
fprintf(stderr, missing )\n);
exit(1);
}
SCAN;
}
else {
r = new(ch, 0, 0);
SCAN;
}
return r;
}
// Tree walker prints simplified expression.
void print(NODE *expr);
void parenthesize(int parent, NODE *expr)
{
if (parent == '*' expr-op == '+') printf(();
print(expr);
if (parent == '*' expr-op == '+') printf());
}
void print(NODE *expr)
{
if (expr-lhs == 0) // leaf node
printf(%c, expr-op);
else {
parenthesize(expr-op, expr-lhs);
printf(%c, expr-op);
parenthesize(expr-op, expr-rhs);
}
}
// Parse one expression per line and print simplified form.
int main(void)
{
while (1) {
SCAN;
if (ch == EOF) return 0;
print(line());
printf(\n);
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: partition a number
On Jul 12, 10:56 am, Tech Id tech.login@gmail.com wrote:
This can be done by recursion.
Each number can be represented as:
N =
1) (N-1), 1
2) (N-2), 2
3) (N-3), 3
N) (1), (N-1)
For each number (N-k), repeat the above in recursion.
You have the right idea, but this recursion scheme will produce many
repeats. Once you have chosen 1 for the right hand operand, for
example, you can avoid repeats by requiring that all other numbers in
the partition be 1 or greater.
Here is C code that implements this strategy. Note I am assuming 0's
are okay in the partition. If 1 is the minimum, then just change the
line in main to
part(10, 4, 1);
---
#include stdio.h
char buf[1024];
int bp;
void part(int n, int m, int min)
{
int i;
if (m == 0 n == 0) {
for (i = bp - 1; i = 0; i--) printf(%d , buf[i]);
printf(\n);
}
else if (m 0) {
for (i = min; i = n; i++) {
buf[bp++] = i;
part(n - i, m - 1, i);
bp--;
}
}
}
int main(void)
{
part(10, 4, 0);
return 0;
}
./a.out
10 0 0 0
9 1 0 0
8 2 0 0
7 3 0 0
6 4 0 0
5 5 0 0
8 1 1 0
7 2 1 0
6 3 1 0
5 4 1 0
6 2 2 0
5 3 2 0
4 4 2 0
4 3 3 0
7 1 1 1
6 2 1 1
5 3 1 1
4 4 1 1
5 2 2 1
4 3 2 1
3 3 3 1
4 2 2 2
3 3 2 2
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] AMAZON Interview Question
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
Can anyone help me with this ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Re: Sub-2Dmatrix maximum
here's an algorithm that can find the the max black rectangle in O(n^3)
here sum[i][j] is the number of contiguous 1s in the ith row from j column
until the end of the row
for (i=0;in;i++){
sum[i][m]=0;
for (j=m-1;j=0;j--){
if (a[i][j]==1)
sum[i][j]=1+sum[i][j+1];
else
sum[i][j]=0;
}
}
so now sum[][] tells us how far we can go on this row
we can check for each possible height for each cell what would be the
maximum rectangle
res=0;
for (i=0;in;i++){
for (j=0;jm;j++){
len=sum[i][j];
for (k=0;k+in;k++){
len=min(len,sum[k+i][j]); // the maximum width is the minimum possible width
among the rows
res=max(res,(k+1)*len); // k+1 is the height of rectangle and len is it's
width
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] 32 comparisons only
good 1. On Tue, Jul 13, 2010 at 2:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: make a bitwise trie since the height would be 32 (number of bits in an integer) u only need 32 comparisons to find an element -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: partition a number
@Gene Please explain the recursive function and the first if condition i m not getting it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Difference b/w two elements in a array
I did not get your point. for 2 6 3 7 min 2 sec min 3 difference is 1 answer is 2 and 3 what more is asked?? On Jul 12, 2:21 pm, srikanth sg srikanthini...@gmail.com wrote: 2 6 3 7 check for this On Mon, Jul 12, 2010 at 12:46 AM, vikas kumar vikas.kumar...@gmail.comwrote: traverse array with 2 elements keeping track of 2 min elements. time O(n) space O(1) On Jul 11, 9:34 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Constraint - O(n) On Sun, Jul 11, 2010 at 9:24 AM, amit amitjaspal...@gmail.com wrote: Given an array of size n.find 2 numbers from array whose difference is least. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 post to this group, send email to algoge...@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.
