Two arrays are arr[] and sec[] To find kth smallest element of the two sorted array. i = 1
1. Find Index = k/(2 ^ i) 2. if arr[Index] < sec[Index] && arr[index] < sec[index -1] then increment index of the first array and decrement the index of second array. i++ 3. if arr[index] > sec[Index] && arr[index] > sec[index-1] then decrement index of the first array and increment the index of second array i++ 4. Step to increment or decrement = K/pow(2,i) Please see the code for more clarity. Let me know if I am missing any corner cases. http://codepad.org/liCpqyqC On Fri, Jun 24, 2011 at 12:55 PM, ankit sambyal <ankitsamb...@gmail.com>wrote: > start thinking as we do in a binary search. > if we want to find the kth smallest no., then compare the k/2 elements > of both the arrays. And depending upon the answer, go for further > iterations.... > Try it out.. Plz ask if u don't understand. I hv just droped a small > hint.... > > > Ankit Sambyal > BITS Pilani > > > > > On Fri, Jun 24, 2011 at 10:50 AM, Akshata Sharma > <akshatasharm...@gmail.com> wrote: > > @Anantha > > can you explain the logic please? > > On Fri, Jun 24, 2011 at 10:21 PM, Anantha Krishnan > > <ananthakrishnan....@gmail.com> wrote: > >> > >> Check this http://ideone.com/C8fQC > >> Thanks & Regards, > >> Anantha Krishnan > >> > >> On Fri, Jun 24, 2011 at 10:18 PM, Decipher <ankurseth...@gmail.com> > wrote: > >>> > >>> Can anybody please explain how to solve this question with logarithmic > >>> time complexity ? > >>> > >>> Write the code/algorithm to find the k-th Smallest Element in the > >>> Union of Two Sorted Arrays . > >>> > >>> -- > >>> 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. > >>> > >> > >> -- > >> 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. > > > > -- > > 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. > > > > -- > 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. > > -- 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.
