are these algos optimal???
*Algo 1*:
no_min_max =-1
min_row= max_row= -1
for(i=0; in; i++)
{
for(j=0; jn; j++){
find min, max
}
if(minprev_min max prev_max){
no_min_max=i;
break;
}
i didnt get it tht even if there are distinct elements how scanning sum
three lines return us the max n min elements? how will this scan whole
matrix for finding the max n min elements???
On Wed, Aug 17, 2011 at 1:32 AM, priya ramesh
love.for.programm...@gmail.com wrote:
are these algos
Hey guys don't panic
original question have unique numbers
palani haven't read the question properly
hence it can be done in O(3n)
On Mon, Aug 15, 2011 at 11:28 AM, shady sinv...@gmail.com wrote:
it will work only if all numbers are unique
On Mon, Aug 15, 2011 at 10:50 AM, Ankur Khurana
Given a n x n matrix. .number are randomly placed. .print any one row which
doesn’t have min
and max elements. Time Complexity : 0(n)
if anyone know the code.. pls share!!!
--
karthikeyankkn
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
how can it be O(n) when there are itself n*n elements..
PS : no sharing of code, else the inevitable
On Sun, Aug 14, 2011 at 11:51 PM, Karthikeyan palani
karthikeyan...@gmail.com wrote:
Given a n x n matrix. .number are randomly placed. .print any one row which
doesn’t have min
and max
sorry O(n^2) s the time complexity
On 14 August 2011 23:56, shady sinv...@gmail.com wrote:
how can it be O(n) when there are itself n*n elements..
PS : no sharing of code, else the inevitable
On Sun, Aug 14, 2011 at 11:51 PM, Karthikeyan palani
karthikeyan...@gmail.com wrote:
Given a n
it can be done in O(3n). in worst case one row will have max and anothr row
will have min so the third row will be your o/p to print
On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani
karthikeyan...@gmail.com wrote:
sorry O(n^2) s the time complexity
On 14 August 2011 23:56, shady
code pls??
On 15 August 2011 00:16, aditya kumar aditya.kumar130...@gmail.com wrote:
it can be done in O(3n). in worst case one row will have max and anothr row
will have min so the third row will be your o/p to print
On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani
no code... algorithm has been stated, implement it urself
On Mon, Aug 15, 2011 at 12:18 AM, Karthikeyan palani
karthikeyan...@gmail.com wrote:
code pls??
On 15 August 2011 00:16, aditya kumar aditya.kumar130...@gmail.comwrote:
it can be done in O(3n). in worst case one row will have max
On 15 August 2011 00:18, Karthikeyan palani karthikeyan...@gmail.comwrote:
code pls??
implement your code, and if you feel that something is wrong with that, then
we can help you out in improving it
On 15 August 2011 00:16, aditya kumar aditya.kumar130...@gmail.comwrote:
it can be done
On 08/14/2011 11:46 AM, aditya kumar wrote:
it can be done in O(3n). in worst case one row will have max and anothr row
will have min so the third row will be your o/p to print
Do you mean O(n^3)?
Consider this { O(n^2) }:
1- Scan the whole matrix and find minimum and maximum entries in
no it is 3*n only read it again
On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavani amir.aav...@gmail.com wrote:
On 08/14/2011 11:46 AM, aditya kumar wrote:
it can be done in O(3n). in worst case one row will have max and anothr
row
will have min so the third row will be your o/p to
it can be done in O(3n). in worst case one row will have max and anothr
row
will have min so the third row will be your o/p to print
Why is that? The min/max element can occur in every row:
1 4 2 10
2 1 10 4
2 3 4 5
1 2 8 10
?
Besides that, you need to scan the whole array to
@shady : does O(3n) include the time required to find the max and min
element as well??
On Mon, Aug 15, 2011 at 12:50 AM, shady sinv...@gmail.com wrote:
no it is 3*n only read it again
On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavani amir.aav...@gmail.comwrote:
On 08/14/2011 11:46
yes
On Mon, Aug 15, 2011 at 12:58 AM, aditi garg aditi.garg.6...@gmail.comwrote:
@shady : does O(3n) include the time required to find the max and min
element as well??
On Mon, Aug 15, 2011 at 12:50 AM, shady sinv...@gmail.com wrote:
no it is 3*n only read it again
On Mon, Aug
just traverse the three rows and get the max and min out of the three rows .
print the row in which their is no max and min .
On Mon, Aug 15, 2011 at 1:02 AM, aditya kumar
aditya.kumar130...@gmail.comwrote:
yes
On Mon, Aug 15, 2011 at 12:58 AM, aditi garg aditi.garg.6...@gmail.comwrote:
some how im not able to get the logic...how will i be able to find max and
min of the entire matrix by jst traversing 3 rows??
for eg
1 2 3 4 5
8 1 3 6 9
4 6 3 2 10
9 0 5 8 12
18 2 6 7 3
fr dis matrix how will u find max and min??
On Mon, Aug 15, 2011 at 1:04 AM, aditya kumar
according to me it would be take 4*n time 3 iterations to choose the
min. and max. from 1st three rows, and n again to print the chosen one
On Mon, Aug 15, 2011 at 1:13 AM, aditi garg aditi.garg.6...@gmail.comwrote:
some how im not able to get the logic...how will i be able to find max and
One approach could be:
I think the min and max elements can be found in n*n*(3n/2)
keep a flag(or array of flag--bitvector ??) for the rows in which min or max
was found
print all other rows for which flag is not set
another n^3(confirm please) algo could be:
sort each row individually
compare
@akssps whatever has been posted is correct
On Mon, Aug 15, 2011 at 1:30 AM, siddharth srivastava
akssps...@gmail.comwrote:
One approach could be:
I think the min and max elements can be found in n*n*(3n/2)
keep a flag(or array of flag--bitvector ??) for the rows in which min or
max
@all: it will take O(3n) for finding max n min and if and only if all
elements in an array are distinct .
On Mon, Aug 15, 2011 at 1:30 AM, siddharth srivastava
akssps...@gmail.comwrote:
One approach could be:
I think the min and max elements can be found in n*n*(3n/2)
keep a flag(or array
@shady : what if all the rows hai one min and one max element , which is
re occurring. your algo doesn't check that
On Mon, Aug 15, 2011 at 1:37 AM, aditya kumar
aditya.kumar130...@gmail.comwrote:
@all: it will take O(3n) for finding max n min and if and only if all
elements in an array are
it will work only if all numbers are unique
On Mon, Aug 15, 2011 at 10:50 AM, Ankur Khurana ankur.kkhur...@gmail.comwrote:
@shady : what if all the rows hai one min and one max element , which is
re occurring. your algo doesn't check that
On Mon, Aug 15, 2011 at 1:37 AM, aditya kumar
23 matches
Mail list logo
