@SoumyaNice Solution.
--
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,
Note that there cannot be more than one celebrity in the group.
Here is an O(n) solution:
Choose a random candidate x as a possible celebrity.
Let S be the set of remaining n-1 candidates.
While (S is not empty)
Remove another candidate y from S and ask if y follows x.
@Saumya, This is a great approach. But it still has a small problem since
there is a non-zero probability (though small) that we need to repeat this
experiment infinitely many times to get a single random number in [1,7]. Is
this the best we can do?
--
You received this message because you
@sharad
Can you explain the O(n*n) + O(n) space algorithm that you
mentioned?
--
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
I found a nice explanation (from some other site) on how to get this formula
T(n) = fib(n+2).
Consider the set of all binary numbers of length n that end with 0. The
first n-1 positions can be anything (0 or 1). So if we take the set of all
binary numbers of length n-1 and append 0 to each of
*What if there are no zero elements at all?*
*
*
*...@minotauraus Very valid question. The terminating condition for the
binary search can be modified to return the count of negative numbers in the
array instead. *
--
You received this message because you are subscribed to
We can do it in O(n * log n) by individually binary-searching for zero on
each of the rows. Once we get the index of the first position where zero
appears, counting the number of negative number is straight-forward.
Here is an even better O(N) algorithm which is very elegant:
Consider the
Hi all,
Please correct me if I am wrong. Since quick sort is in-place
sort, there is no difference in stack space whichever order you do it. In
the worst case the stack depth can be O(n) unless you convert the quick sort
of longer sub-array to iteration instead of recursion in which
@Jitendra: Catalan number grows at least exponentially:
http://mathworld.wolfram.com/CatalanNumber.html
--
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
Same question with interesting answers in stackoverflow :
http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists
On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote:
Well, in that case, then just forget the balancing the
10 matches
Mail list logo