A simple modification to quicksort will do the trick !
On 11/13/07, geekko [EMAIL PROTECTED] wrote:
you are given an array of integers containing only 0s and 1s. You have
to place all the 0s in even positions and 1s in odd position. And if
suppose, no. of 0s exceeds no. of 1s or vice versa
Can you explain the modification?
--~--~-~--~~~---~--~~
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
@Dave,
*Otherwise, set the even position to 0 and the odd position to 1.*
I think your solution might be inserting 0's and 1's into the array from
nowhere (thus filling the whole array with alternating 0's and 1's up to the
given size !). The question is to re-arrange existing elements in the
Thank you, I understood the question wrong. I thought if the # of 0's
or #1's exceeded each other, the whole array would be untouched. So i
couldn't solve it in one pass.
On 13 Kasım, 16:15, Dave [EMAIL PROTECTED] wrote:
The following algorithm examine the contents of each element of the
array
No. At step 6, we have found a 1 in an even spot and a 0 in an odd
spot, so we switch them. Switching a 1 and a 0 simply means storing 0
where the 1 was and storing 1 where the 0 was; there is no need to use
the usual code to interchange two values.
Dave
On Nov 13, 8:37 am, Vikram Venkatesan
No. You have the ! in the wrong spot. It should be LOG (N!), not LOG
(N)!. The factorial function (operator) is defined only for integers.
Then, again, question 2 should be
2) What is relationship betweenLOG(N!) and NLOGN?
Dave
On Oct 22, 2:31 pm, Allysson Costa [EMAIL PROTECTED]
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Do a binary search in each row or column. If there are m rows and n
columns, this is O(m log n) or O(n log m), respectively.
Dave
On Nov 13, 10:11 am, geekko [EMAIL PROTECTED] wrote:
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
On Nov 13, 11:11 am, geekko [EMAIL PROTECTED] wrote:
Given a matrix all whose columns and rows are individually sorted, how
do you search a number in it?
Of course there are many ways. I assume you want to minimize work.
You can start in the upper right hand corner and go left or down in
It looks good.
Have you done some experiments to test its efficiency?
Maybe (1) is not such a strong branch-cutting condition as you think.
See sequence like below:
P[p], P[1]*P[2]*...*P[p-1] *(P[p]-1), P[1]*P[2]*...*P[p-1] *(P[p]-2) ,
..., P[1]*P[2]*...*P[p-1] *(1)
It need branch on every
I made a mistake while constructing worst case input.
Just ignore it.
On Nov 14, 2007 11:50 AM, hongcheng zhu [EMAIL PROTECTED] wrote:
It looks good.
Have you done some experiments to test its efficiency?
Maybe (1) is not such a strong branch-cutting condition as you think.
See sequence like
@Dave,
Ya. You are right. I think i overlooked your solution. The step 'set the
even position to 0...' sounded like, setting 0 and 1 directly :-)
Thanks,
Vikram
On 11/13/07, Dave [EMAIL PROTECTED] wrote:
No. At step 6, we have found a 1 in an even spot and a 0 in an odd
spot, so we
12 matches
Mail list logo
