for Q1. you can do it in o(n) time Call your missing number M. You can split your array into two parts depending on whether the least significant bit of A[i] is a 1 or a 0. The smaller of the two parts (call it P_1) is at most (n-1)/2 elements in size, and it tells you whether M's least significant bit is a 1 or a 0.
Now consider the 2nd bit for the elements of P_1. Again, this part can be split in two, and the smaller of the two parts (P_2) tells you whether this bit should be a 1 or a 0. Carry on going (P_3, P_4, ...) until you've worked out what all the bits are. Regards Priyaranjan http://code-forum.blogspot.com On Jan 16, 9:09 pm, Decipher <ankurseth...@gmail.com> wrote: > Q1)An array A[1 n] contains all the integers from 0 to n except for one > number which is missing . In this problem, we cannot access an entire > integer in A with a single operation . The elements of A are represented in > binary, and the only operation we can use to access them is “fetch the jth > bit of A[i]”, which takes constant time Write code to find the missing > integer . Can you do it in O(n) time? > > Q2)Given an integer, print the next smallest and next largest number that > have the same number of 1 bits in their binary representation . -- 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.
