Kevin wrote: > I get what Terry means now. But it still uses 625/800 = 78% of the > naive method in terms of diskspace (or memory, whatever), so I think > the save is not big enough (the job interview is R&D targeted, which I > assume they want to hear one with "large" saving). > > Prateek's idea is to reduce the time of whole set read in (suppose they > are saved to disk since there are many of them). It should work if the > give k does not show up frequently. For each k, on average, I think we > only need to read in 200/5000 = 4% percent of the whole sets, on 96% > times we only need to check the begining and ending index. But I am > kind of worry for the step 4), which will vary the value of k for many > times. > > beelzebub mentioned "co-prime", interesting. I will think a little bit > more of it.
Well it should be 200 numbers randomly chosen not randomly chosen from the initial set :) As you are checking all the numbers of all the sets , when you randomly choose a number why don't check if it is in the bitstring and then discard it. I am not saving anything other than the bitstring. Well i think you need them to be prime, because all the prime factors of a number x ( any number which is not prime ) will be present . --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
