[algogeeks] Re: O(n) Time is the problem. ..

@Anonymous: There are 6 numbers in the list. The low order bit of 1^2^3^4^5^6 is 1. The low order bits of the input are 0,1,0,1,1,0. As you read them, make a list pointers to the numbers that have low order bit 0 and another list of pointers that have low order bit 1, and also take their exclusive

[algogeeks] Re: O(n) Time is the problem. ..

@Dave Can you please explain through example. Suppose the set is {0,1,2,3,5,6} Then how this solution proceeds. I am partially getting the logic you explained but need to see an example. Thanks!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" grou

Re: [algogeeks] Re: O(n) Time is the problem. ..

For the code, here u go http://ideone.com/js1yV On Wed, Jun 29, 2011 at 10:49 AM, Dave wrote: > @Sanket: You are wrong. Let T(n) be the time to solve the problem of > size n. Then T(n) satisfies a recurrence T(n) = n + T(n/2). That is > because after you have done n reads, you have determined wh

[algogeeks] Re: O(n) Time is the problem. ..

@Sanket: You are wrong. Let T(n) be the time to solve the problem of size n. Then T(n) satisfies a recurrence T(n) = n + T(n/2). That is because after you have done n reads, you have determined whether the last bit is 0 or 1. To continue the solution, you only need to consider those numbers that ha

Re: [algogeeks] Re: O(n) Time is the problem. ..

Suppose after first iteration, I iterate through whole array XORring+(1..N) the last bit and I get 1. Now, for making sure I don't need process undesirable numbers with last bit '0', I will need to use sum bool array of size N bits to discard those numbers or I can do it without using it? Explanat

[algogeeks] Re: O(n) Time is the problem. ..

@Sunny - I would disagree. Assume there is a nested loop iterating over an array and for every iteration of the outer loop, you are reducing the number of elements accessed in the inner loop into half. So, in the first iteration of the outer loop, you access n elements in the inner loop, in the sec

Re: [algogeeks] Re: O(n) Time is the problem. ..

http://anandtechblog.blogspot.com/2011/06/google-question-find-missing-number.html On Mon, Jun 27, 2011 at 4:12 PM, aditya kumar wrote: > > @Kamakshi.thnks.i dint realise that. > > On Mon, Jun 27, 2011 at 11:04 PM, sunny agrawal > wrote: > >> @saket - No >> >> O(n) + O(n/2) + O(n/4)

Re: [algogeeks] Re: O(n) Time is the problem. ..

@Kamakshi.thnks.i dint realise that. On Mon, Jun 27, 2011 at 11:04 PM, sunny agrawal wrote: > @saket - No > > O(n) + O(n/2) + O(n/4)... = O(n) > > sum of series > n+n/2+n/4+n/8 = 2n > > > On Mon, Jun 27, 2011 at 9:26 PM, Sanket wrote: > >> @Dave - Wouldn't your soluti

Re: [algogeeks] Re: O(n) Time is the problem. ..

@saket - No O(n) + O(n/2) + O(n/4)... = O(n) sum of series n+n/2+n/4+n/8 = 2n On Mon, Jun 27, 2011 at 9:26 PM, Sanket wrote: > @Dave - Wouldn't your solution also become O(kn) where k = number of > bits in the number? > In this summation - O(n) + O(n/2) + O(n/4) + .

[algogeeks] Re: O(n) Time is the problem. ..

@Dave - Wouldn't your solution also become O(kn) where k = number of bits in the number? In this summation - O(n) + O(n/2) + O(n/4) + ...= O(n) - you would have O(n) appearing 'k' times. Each entry is O(n/ 2^i) where 'i' is the bit position from right to left, starting at 0. The range of 'i' is fro

Re: [algogeeks] Re: O(n) Time is the problem. ..

can anyone plz post the code for this problem -- 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.c

[algogeeks] Re: O(n) Time is the problem. ..

@Sanket: Yes. That is the first O(n) in my previous posting http://groups.google.com/group/algogeeks/msg/cd32a2276c6a2d22. Dave On Jun 26, 6:55 pm, Sanket wrote: > Thanks Dave. > > Won't "Also, calculate the xor of the low order bits of the data" > require you to access each value in the array o

[algogeeks] Re: O(n) Time is the problem. ..

Thanks Dave. Won't "Also, calculate the xor of the low order bits of the data" require you to access each value in the array once? Or am I not understanding what you meant? On Jun 26, 6:50 pm, Dave wrote: > @Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the > last two bits of N

[algogeeks] Re: O(n) Time is the problem. ..

@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the last two bits of N need be considered, i.e., N & 3. You could index into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so the expression can be evaluated with bit operations by (6 >> (N & 3)) & 1. Also, calculate the

[algogeeks] Re: O(n) Time is the problem. ..

Dave - Can you elaborate on how you can do this - "you can determine whether the low order bit of the missing number is 0 or 1" On Jun 26, 2:32 pm, Kamakshii Aggarwal wrote: > thanks dave.. > > On 6/26/11, Dave wrote: > > > @Kamakshii: In O(n), you can determine whether the low order bit of > >

Re: [algogeeks] Re: O(n) Time is the problem. ..

thanks dave.. On 6/26/11, Dave wrote: > @Kamakshii: In O(n), you can determine whether the low order bit of > the missing number is 0 or 1. You can eliminate the approximately n/2 > numbers that do not have this low order bit. Then, in O(n/2), you can > determine the next-to-low order bit. Etc. O

[algogeeks] Re: O(n) Time is the problem. ..

@Kamakshii: In O(n), you can determine whether the low order bit of the missing number is 0 or 1. You can eliminate the approximately n/2 numbers that do not have this low order bit. Then, in O(n/2), you can determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ... = O(n). Dave On Ju

Re: [algogeeks] Re: O(n) Time is the problem. ..

@dave:can u please give the divide and conquer solution On 6/26/11, Kamakshii Aggarwal wrote: > @aditya:it is given in the question that u cannot access the entire > element in single operaion..therefore both your above solution do not > hold for this question. > > On 6/25/11, sunny agrawal wrot

Re: [algogeeks] Re: O(n) Time is the problem. ..

@aditya:it is given in the question that u cannot access the entire element in single operaion..therefore both your above solution do not hold for this question. On 6/25/11, sunny agrawal wrote: > @Dave > yes u r right that integers means it can be big integers too. > generally when we talk about

Re: [algogeeks] Re: O(n) Time is the problem. ..

@Dave yes u r right that integers means it can be big integers too. generally when we talk about integers, they are 32 bit integers in Programing/Algorithm Questions so i was assuming that here and about my solution - yes it will be O(nlgn) or O(nw) not acceptable for given Q :( and yes a Divide

[algogeeks] Re: O(n) Time is the problem. ..

@Sunny. You are reading too much into that. There is no mention that the data are 32-bit integers. Perhaps they are big integers. What we know is that the data are not characters, real numbers, rational numbers, floating point, etc. Your algorithm is O(n*w), where w is the word size. As I said, a

Re: [algogeeks] Re: O(n) Time is the problem. ..

@Dave it is given in Question that elements of array are integer On Sat, Jun 25, 2011 at 7:17 AM, Dave wrote: > @Sunny: What makes you think that the integers are 32 bits in length. > Remember that O(.) notation applies as n --> infinity. Thus, O(n log > n) is correct for a naive algorithm. But

[algogeeks] Re: O(n) Time is the problem. ..

@Sunny: What makes you think that the integers are 32 bits in length. Remember that O(.) notation applies as n --> infinity. Thus, O(n log n) is correct for a naive algorithm. But a little thought can give a divide-and-conquer algorithm which is O(n). Dave On Jun 24, 8:44 am, sunny agrawal wrote

Re: [algogeeks] Re: O(n)

Finding the range(min & max) of an array takes O(n). So that is not an issue. But if the array is sparse i.e. very few elements in a large range, then this method would not be effective considering space utilization. -Abhirup On Mon, Jun 28, 2010 at 2:28 PM, Abhishek Sharma wrote: > may be to f

Re: [algogeeks] Re: O(n)

may be to figure out the range while reading the numbers or taking the mos as input... we can have two variables (min and max) that contains the minimum and maximum elements encountered so far respectively... i.e. whenever we read a no n we compare it with min and max... if nmax then max = n; so t

Re: [algogeeks] Re: O(n)

i agree with nisha ,if range is not given then count sort is not applicable..can we apply radix sort bcoz it is also O(kn)...n if we assume k

Re: [algogeeks] Re: O(n)

@abhirup: range is required in counting sort how can you decide that?? please elaborate On Mon, Jun 28, 2010 at 12:01 PM, Abhirup Ghosh wrote: > We can sort the array in O(n) time using counting sort. And then take > the difference of consecutive elements in O(n) time to get the minimum

Re: [algogeeks] Re: O(n)

i also think o(n) is not possible but it was asked by amazon . -- 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+unsub

Re: [algogeeks] Re: O(n)

@abhirup: I agree with ur idea of sorting and then finding out the difference for the consecutive elementsbut counting sort takes the range into account.. I dont think range is given... On Mon, Jun 28, 2010 at 12:01 PM, Abhirup Ghosh wrote: > We can sort the array in O(n) time using counting

Re: [algogeeks] Re: O(n)

Thats possible only if we know the range.. On Mon, Jun 28, 2010 at 12:01 PM, Abhirup Ghosh wrote: > We can sort the array in O(n) time using counting sort. And then take > the difference of consecutive elements in O(n) time to get the minimum > one. > > -Abhirup > > > > On Mon, Jun 28, 2010 at 1

Re: [algogeeks] Re: O(n)

We can sort the array in O(n) time using counting sort. And then take the difference of consecutive elements in O(n) time to get the minimum one. -Abhirup On Mon, Jun 28, 2010 at 10:36 AM, Jagadish M wrote: > In the general case, we can reduce Element-Distinctness(ED) problem to > this problem

[algogeeks] Re: O(n)

In the general case, we can reduce Element-Distinctness(ED) problem to this problem. Since ED has a lower bound of Omega(n log n), we cannot get an O(n) algorithm for this problem. http://en.wikipedia.org/wiki/Element_distinctness_problem -Jagadish http://www.cse.iitb.ac.in/~jagadish On Jun 2