is this contest still going? if so, where ? i have a solution that does (100, 1267650600228229401496703205376 ) (just one hundred 1's) in 0.03 seconds in an older ruby on an older pc
I'd like to submit ;P On Oct 21, 10:48 pm, sunny agrawal <sunny816.i...@gmail.com> wrote: > yea i know 1st Approach is much better and is Only O(N^2) for > precomputing all the values for nck and then O(k) for finding no of > bits set in The Kth number and another loop of O(k) to find the > required number > > i posted 2nd approach in the context to vandana's tree approach of > sorting 2^N numbers, rather simply sort the numbers in the array... > and this approach is O(N*2^N) > > On 10/21/11, sravanreddy001 <sravanreddy...@gmail.com> wrote: > > > > > > > > > > > @Sunny.. why do we need an O(2^N) complexity? > > > for a value of N=40-50, the solution is not useful.. > > > but, your 1st approach is lot better and i have got it too.. > > > 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1->k > > (n C i)) > > 2. again, keep substracting (k-i) for i= 0->k-1 so.. O(k) here > > and recursively performing step 2. (worst case complexity is O(T)) > > where T = nCk > > > O(N) + O(T) ==> O(T) as it dominates the given number. unless it doesn't > > fall in the range.. or equivalently --> max( O(T), O(N) ) > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To view this discussion on the web visit > >https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J. > > 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. > > -- > Sunny Aggrawal > B.Tech. V year,CSI > Indian Institute Of Technology,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.
