If N is big enough so that all data will not fit in main memory and k
is small enough so that the k top elements fit in memory, then the
heap is likely to be the best.This is because disk access is so
incredibly slow compared to memory access: A few milliseconds (10^-3)
vs. a few nanoseconds
there was error in else part and one more while loop was missing :-
here is the correct algo:-
while(!isEmpty(s1) || !isEmpty(s2))
{
while(!isEmpty(s1))
{
val=pop(s1);
print : val-data;
@ania
My idea is based on the post that i had replied in
http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b?hl=en#
A simple tweak to the above algo can be used to solve bin-packing
problem in a (probably) faster time. First, please go through the
above post.
The
A slightly different approach on the lines of data access and ease of
understanding:
1) Sort the input array i.e the weights array W[N] .
2) Identify the no. of unique elements in it and create the following:
a) Count[R] - count of each unique element based on its sorted
order.
@ Gaurav
I don't think the above nlogn approach will work. If i m not wrong,
the above nlogn approach is a modification of the nlogn algo for
maximum continuous subset problem.
I have a doubt with the crossing subarray solution. I see that your if
and while loop breaks out if totalsum =K is not
Given an array of elements find the largest possible number that can
be formed by using the elements of the array
eg: 10 9
ans: 910
eg: 2 3 5 78
ans: 78532
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Sort the numbers based on the 'index_position' (starting at most significat
digit) -- a modified version of MSD radix to be used.
or sort the numbers as sorting the strings, (print all in desc order).
--
You received this message because you are subscribed to the Google Groups
Algorithm
+1 @sravan
On Dec 12, 8:55 pm, sravanreddy001 sravanreddy...@gmail.com wrote:
Sort the numbers based on the 'index_position' (starting at most significat
digit) -- a modified version of MSD radix to be used.
or sort the numbers as sorting the strings, (print all in desc order).
--
You
Hi every one.
Can we find largest number from an unsorted array in log(n) ?
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I think...
First round of tournament sort. :D
On Mon, Dec 12, 2011 at 8:02 AM, sagar pareek sagarpar...@gmail.com wrote:
Hi every one.
Can we find largest number from an unsorted array in log(n) ?
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
@Sravanreddy: There is more to it, as the cases {865, 86, 7} and {865,
86, 2} show.
Dave
On Dec 12, 9:55 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Sort the numbers based on the 'index_position' (starting at most significat
digit) -- a modified version of MSD radix to be used.
or
@sravan- Sorting would fail in this case:
consider 8,91, 9
sorting in desc order is going to give us 91, 9, 8.
printing this is going to give us 9198.
However, a bigger number can be formed 9891.
After sorting lexicographically, we have to consider whether tied
elements in list can be combined
Yes Mr. DoN
First round of Tournament sort results in log(n) time for finding largest
no.
n/2+n/4+n/8 results n/(2^i) where ^ = power
On Mon, Dec 12, 2011 at 8:16 AM, Don dondod...@gmail.com wrote:
No. To find the largest number in an unsorted array requires looking
at
@Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first
round, involving n/2 comparisons, is O(n).
Dave
On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote:
Yes Mr. DoN
First round of Tournament sort results in log(n) time for finding largest
no.
n/2+n/4+n/8
If for a number n digits long, the absolute difference between
adjacent digits is given, how to find out the number of different
numbers with these absolute differences ?
for eg,
if n=5
and the absolute differences are
3 2 5 1
then 1 possible number is
6 3 5 0 1(because |6-3|=3,|3-5|=2 and so
Agree with dave..Its still O(n)
On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote:
@Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first
round, involving n/2 comparisons, is O(n).
Dave
On Dec 12, 11:23 am, sagar pareek sagarpar...@gmail.com wrote:
Yes Mr.
Thinking on the same lines:
1) First sort the array in descending order.. A[n]
2) Use the following equation solve the prob:
L(n) = the largest no. that can be formed by placing the A[n] in
(n-2) possible positions of L(n-1)...
Complexity : O(nlogn) + O(n^2)
What do u guys think?
On Dec
@above..
just to add to the above post... L(n) is basically reordering of the
elements of A[n] which would produce the largest possible integer when
read from L(0) to L(n).
On Dec 12, 11:07 pm, Lucifer sourabhd2...@gmail.com wrote:
Thinking on the same lines:
1) First sort the array in
apply MAXHEAPIFY on root ode and extract the root node
--
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
Max Heapify is O(n).
On Mon, Dec 12, 2011 at 11:43 PM, ankit gupta ankit.itc...@gmail.comwrote:
apply MAXHEAPIFY on root ode and extract the root node
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
thanx Anika..
--
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,
@rahul
we post these qus bcos in this group lots of members r there.
--
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
maxheapify is lg(n)..check coremen
--
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
http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sorting/heapSort/heapSort.html
for reference
--
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,
Guys, if you can find a solution that is not exponential time in the
worst case you are going to be famous because this problem is NP-Hard
in the strong sense. I.e. there is not even a pseudo-polynomial time
algorithm. To get a perfect solution every time, you can't do better
than heuristic
^it cant get better than O(n) apparently. Just applying max-heapify once
would not yield the max element. You need to construct a heap for it, which
is no less than O(n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
@Gene
Great information.. Wasn't aware of the above cited finding...
Thanks..
@ For all active followers of this post..
The problem posted by ania is a slight modification of the bin-packing
problem as pointed out above because here the no. of bins to be filled
is fixed and the capacity (of the
Exactly. Really you should see this with almost no thought. It's
called an adversary argument and goes like this.
Since you don't know the order of elements in A, envision them as
being put in order by an adversary that always knows in advance what
element you're going to examine next. Now no
By Max Heapify I thought u meant to say u are making a Max Heap .. In case
you use Coreman Definition Of max Heapify it just heapifies assuming the
heap has been formed, But u need to make a max Heap first dude :)
P.S- Clarify your concepts before posting the link :(
On Tue, Dec 13, 2011 at
@Kay: 9918 is bigger than 9891. :-)
Dave
On Dec 12, 11:23 am, KAY amulya.manches...@gmail.com wrote:
@sravan- Sorting would fail in this case:
consider 8,91, 9
sorting in desc order is going to give us 91, 9, 8.
printing this is going to give us 9198.
However, a bigger number can be
@Kay:
In the algo given above i don't think sorting is required...Only the
following is enough..
Use the following equation solve the prob:
L(n) = the largest no. that can be formed by placing the A[n] in
(n-2) possible positions of L(n-1)...
Complexity : O(n^2)
On Dec 13, 3:07 am, Dave
An nlogn approach... would require validation from others..
Normal sorting in decreasing order shall solve this problem with one
modification which is a special case and i.e.
if 2 nos. to be sorted are in the following format:
abc and abcX ... where X itself is a number of the form (def...)
@all..Well I am no expert but my logic says its impossible to pick the best
unless and untill you look at each and every individual.Isn't this logic
enough?
On Tue, Dec 13, 2011 at 12:32 AM, Ankur Garg ankurga...@gmail.com wrote:
By Max Heapify I thought u meant to say u are making a Max Heap
only the number of comparisons is log(n)
On Mon, Dec 12, 2011 at 11:04 PM, Ankur Garg ankurga...@gmail.com wrote:
Agree with dave..Its still O(n)
On Mon, Dec 12, 2011 at 10:57 PM, Dave dave_and_da...@juno.com wrote:
@Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first
round,
@kay bigger number is 9918 not 9891...
On Mon, Dec 12, 2011 at 11:39 PM, Lucifer sourabhd2...@gmail.com wrote:
@above..
just to add to the above post... L(n) is basically reordering of the
elements of A[n] which would produce the largest possible integer when
read from L(0) to L(n).
On Dec
for ababc - ab is common..so removing ab we get abc.
then in abcabc - abc is commonso removing abc we get abc ?? what is
the difference in this case
On Mon, Dec 12, 2011 at 7:52 PM, top coder topcode...@gmail.com wrote:
For example if aabbabc is given as input after first iteration, it
question is not clear...plz specify clearly what's the objective..
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99
+1 amol sharma...what u want ??.output should be shown at every
step or u want final ans??
--
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
@Lucifer : if i am not getting it wrong then are you trying to say find
all permutation of the given number ??
On Mon, Dec 12, 2011 at 11:39 PM, Lucifer sourabhd2...@gmail.com wrote:
@above..
just to add to the above post... L(n) is basically reordering of the
elements of A[n] which would
well 1st part can be done of removing similar character ,
for the 2nd iteration where you want to remove continuous duplicate sub
string then i guess this can be done :-
for example :-
input : aabbabc
1st iteration : ababc
for 2nd iteration consider queue
1) maintain front value inserted int
@Lucifer (Regarding your latest approach) - I guess you meant string based
comparison sort in the first step, as in 9 would be greater than 10. The
special case seems correct but I doubt the complexity being nlog n,
considering the special case.
--
You received this message because you are
You are right the algorithm is based on the max subarray problem. The
difference is the logic to get the crossingSubArray() method. The way it works
is like this:
The outer while loop, makes sure that left position or right position at least
one of this should be between lo and hi values
42 matches
Mail list logo
