Re: [algogeeks] Re: Maximize Subsquare
@Dark prince : what is meant by Allones(i,0.k) what subsquare he is considering here?? On 22 November 2011 23:57, DarkPrince darkprince...@gmail.com wrote: It means that the Borders of the mavximum rectangle should hav all 1s irrespective the elements inside the rectangles , it can be either 0 or 1 . -- 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 Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: finding closest points
Exactly. But I think you can get O(n) by using the linear time K- median selection algorithm (see for example http://en.wikipedia.org/wiki/Selection_algorithm) on the distances to the target point. These kinds of questions where you process all n points every time are seldom of practical interest. What is usually wanted is to build a query data structure once in O(n), O(n log n) or even O(n^2) time and then handle repeated queries and individual updates in O(log n) or O(1) time. The classic example is a kd-tree. On Nov 22, 2:31 pm, Dave dave_and_da...@juno.com wrote: @Aamir: But assuring that k = n/2 isn't the same thing as saying that k O(n). Note that if k = n/2, then O(n log k) = O(n log n). Dave On Nov 22, 10:38 am, Aamir Khan ak4u2...@gmail.com wrote: On Tue, Nov 22, 2011 at 8:43 PM, Dave dave_and_da...@juno.com wrote: @Ganesha: You could use a max-heap of size k in time O(n log k), which is less than O(n log n) if k O(n). We can always ensure that k = n/2. If k = n/2 then the problem can be stated as, find m points farthest from the given point by creating min-heap of size m. The elements which were present in input but not in heap will be the points nearest to the given point, where m = n-k. Dave On Nov 22, 8:56 am, ganesha suresh.iyenga...@gmail.com wrote: Given a set of points in 2D space, how to find the k closest points for a given point, in time better than nlgn. -- Aamir Khan | 3rd Year | Computer Science Engineering | IIT Roorkee -- 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.
[algogeeks] Recurrence relation
When i try to solve this T(n) = 2T(n/2) + 2 recurrence relation i get order N. But http://www.geeksforgeeks.org/archives/4583 claims that it is 3/2n-2. The order is still N only but how do we get the constants ? -- 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.
[algogeeks] Re: An Array Problem
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.comwrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order. Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search. Pop
out all these elements and assign the value m in the output array. Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
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.
--
Aamir Khan | 3rd Year | Computer Science Engineering | IIT Roorkee
--
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.
Re: [algogeeks] Re: An Array Problem
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
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.
--
Aamir Khan | 3rd Year | Computer Science Engineering | IIT Roorkee
--
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
Re: [algogeeks] Re: An Array Problem
Here is my code with logic techcoder described ...
void PushSmallerElement(int a[],int n){
stackpairint,int s;
pairint,intp;
int top;
for(int i=0;in;i++){
if(s.empty())
s.push(pairint,int(a[i],i));
else{
p=s.top();
while( !s.empty() a[i]p.first ){
s.pop();
a[p.second]=a[i];
p=s.top();
}
}
s.push(pairint,int(a[i],i));
}
while(!s.empty()){
p=s.top();
s.pop();
a[p.second]=0;
}
}
On Wed, Nov 23, 2011 at 3:43 PM, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search.
Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win ,
the
more successfully u play*
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this
[algogeeks] Re: Recurrence relation
Solving recurrences is an art form. There are many techniques. One of the simplest is to assume you know the form of the result with some unknown coefficients. Then plug the form into the recurrence and try to solve for the coefficients. If you succeed, you're done. If not, look for another form or an entirely different technique. Here we assume T(n) = an + b. Substitute: T(n) = an + b = 2T(n/2) + 2 = 2[ a(n/2) + b ] + 2 = an + 2b + 2 Now subtracting an+b from both sides we have b = -2. To find a, we need the base case. With T(2) = 1, we have T(2) = an + b = a(2) - 2 = 1 This produces a = 3/2, so T(n) = 3/2 n - 2 as stated. On Nov 23, 3:59 am, Ankuj Gupta ankuj2...@gmail.com wrote: When i try to solve this T(n) = 2T(n/2) + 2 recurrence relation i get order N. But http://www.geeksforgeeks.org/archives/4583 claims that it is 3/2n-2. The order is still N only but how do we get the constants ? -- 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.
[algogeeks] Re: An Array Problem
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
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*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more successfully u play*
--
You
Re: [algogeeks] Re: An Array Problem
It's a variation of next greater element problem (
http://www.geeksforgeeks.org/archives/8405). Instead of next greater
element, this problem asks about next smaller element.
On Wed, Nov 23, 2011 at 5:29 PM, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder
techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the
right.
put the first element in stack.
take next element suppose num if this number is less than
elements
stored in stack, pop those elements , for these pooped elements
num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit
the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted
order.
Get
a new element from array and lets call this number as m. Push m into
the
stack. Now, find all elements which are = (m-1) using binary
search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group,
[algogeeks] Re: An Array Problem
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p=0, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0 (valaue)
@techcoder : If the numbers are not in sorted order, What benefit the
stack would provide ? So, are you storing the numbers in sorted order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted order.
Get
a new element from array and lets call this number as m. Push m into the
stack. Now, find all elements which are = (m-1) using binary search.
Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than
input[i] and jth is nearest to ith ( i.e. first element which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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.
--
Anup Ghatage
--
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
[algogeeks] Any one
You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- Abhishek Kumar B.Tech(IT) Graduate Allahabad Contact no-+919663082731 -- 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.
Re: [algogeeks] Re: An Array Problem
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p=0, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and
its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an element,
it's too big to maintain the invariant, so it must be popped! We can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder
techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the
right.
put the first element in stack.
take next element suppose num if this number is less than
elements
stored in stack, pop those elements , for these pooped elements
num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0
(valaue)
@techcoder : If the numbers are not in sorted order, What
benefit the
stack would provide ? So, are you storing the numbers in sorted
order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted
order.
Get
a new element from array and lets call this number as m. Push m
into the
stack. Now, find all elements which are = (m-1) using binary
search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage
ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta
ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
correspondence.
output[i] is equal to the input[j] (ji) which is smaller
than
input[i] and jth is nearest to ith ( i.e. first element which
is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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
[algogeeks] Re: Recurrence relation
Thanx Gene. Is there any other method than master's thm ? On Nov 23, 4:13 pm, Gene gene.ress...@gmail.com wrote: Solving recurrences is an art form. There are many techniques. One of the simplest is to assume you know the form of the result with some unknown coefficients. Then plug the form into the recurrence and try to solve for the coefficients. If you succeed, you're done. If not, look for another form or an entirely different technique. Here we assume T(n) = an + b. Substitute: T(n) = an + b = 2T(n/2) + 2 = 2[ a(n/2) + b ] + 2 = an + 2b + 2 Now subtracting an+b from both sides we have b = -2. To find a, we need the base case. With T(2) = 1, we have T(2) = an + b = a(2) - 2 = 1 This produces a = 3/2, so T(n) = 3/2 n - 2 as stated. On Nov 23, 3:59 am, Ankuj Gupta ankuj2...@gmail.com wrote: When i try to solve this T(n) = 2T(n/2) + 2 recurrence relation i get order N. But http://www.geeksforgeeks.org/archives/4583 claims that it is 3/2n-2. The order is still N only but how do we get the constants ? -- 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.
[algogeeks] Does Y lies between x and z
There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- 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.
[algogeeks] Re: Recurrence relation
The Masters Thm covers only a certain family of recurrences. There are many others. Solving recurrences is comparable to finding analytical solutions to differential equations except that recurrences aren't as important in mathematical analysis, so aren't studied as much. I am not an expert, but there is a rich theory of generating functions that is widely regarded as a powerful tool for solving recurrences. The guess and confirm method that I described is covered in more detail in http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/99-recurrences.pdf Gene On Nov 23, 12:58 pm, Ankuj Gupta ankuj2...@gmail.com wrote: Thanx Gene. Is there any other method than master's thm ? On Nov 23, 4:13 pm, Gene gene.ress...@gmail.com wrote: Solving recurrences is an art form. There are many techniques. One of the simplest is to assume you know the form of the result with some unknown coefficients. Then plug the form into the recurrence and try to solve for the coefficients. If you succeed, you're done. If not, look for another form or an entirely different technique. Here we assume T(n) = an + b. Substitute: T(n) = an + b = 2T(n/2) + 2 = 2[ a(n/2) + b ] + 2 = an + 2b + 2 Now subtracting an+b from both sides we have b = -2. To find a, we need the base case. With T(2) = 1, we have T(2) = an + b = a(2) - 2 = 1 This produces a = 3/2, so T(n) = 3/2 n - 2 as stated. On Nov 23, 3:59 am, Ankuj Gupta ankuj2...@gmail.com wrote: When i try to solve this T(n) = 2T(n/2) + 2 recurrence relation i get order N. But http://www.geeksforgeeks.org/archives/4583 claims that it is 3/2n-2. The order is still N only but how do we get the constants ? -- 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.
Re: [algogeeks] Any one
yes levenshtein distance and BK tree can be used to solve this. where edge weight between nodes is equal to levenshtein distance. On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar afs.abhis...@gmail.comwrote: You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- Abhishek Kumar B.Tech(IT) Graduate Allahabad Contact no-+919663082731 -- 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 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] Finding the repeated element
In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Finding the repeated element
Only possible best solution seems to be sorting the array using median selection algorithm ( a varient of quicksort) and then comparing to find the elements. Cheers, Ankit!!! On Thu, Nov 24, 2011 at 11:32 AM, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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 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] Finding the repeated element
@ankit : I think ur solution does not work because if the array is 4 2 8 9 5 1 9 sorting: 1 2 4 5 8 9 9 median is 5 ,but i want 9 as the answer that to median finding algorithm is O( n logn). On 23 November 2011 23:09, Ankit Sinha akki12...@gmail.com wrote: Only possible best solution seems to be sorting the array using median selection algorithm ( a varient of quicksort) and then comparing to find the elements. Cheers, Ankit!!! On Thu, Nov 24, 2011 at 11:32 AM, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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 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 Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: Finding the repeated element
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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.
