Re: [algogeeks] Re: Finding the repeated element
@kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted. -- 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.
Re: [algogeeks] Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
http://www.geeksforgeeks.org/archives/8858 On 24 November 2011 01:06, Ankuj Gupta ankuj2...@gmail.com wrote: Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
char arr[] = {'a', 'b', 'e', 'f', 'd', 'g', 'h', 'i'};
calculate the point where array is not sorted , in this case arr[4] =
'd'
calulate k in array[5..n] such that k 4 arr[k] d , take the min =
min{ arr[k] }
same thing for max from reverse
use quick /selection sort to identify the correct insertion indices of
min/max, that will be answer.
complexity O(n)
On Nov 24, 2:06 pm, Ankuj Gupta ankuj2...@gmail.com wrote:
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
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.
[algogeeks] Re: Finding the repeated element
I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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.
Re: [algogeeks] Re: Finding the repeated element
hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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.
Re: [algogeeks] Re: Finding the repeated element
@ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Re: Finding the repeated element
find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Re: Finding the repeated element
@shady : i am not sure , if u can do it with O(n) space as well it is fine for me . but once try whether it is possible in O(1) space. On 24 November 2011 05:42, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Re: Finding the repeated element
i also doubt about the time and space complexity of the problem, i has been asked a number of times with these constraints but never been answered the required, as far as i remember the best solution to this problem that has been discussed so far is using hashing and that too theoretically having TC and SC of O(n). On Thu, Nov 24, 2011 at 7:12 PM, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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.
Re: [algogeeks] Re: Finding the repeated element
i don't think there is an O(n) time solution for this... bcoz there are no constraints on the values, and on the number of values in the array. On Thu, Nov 24, 2011 at 7:15 PM, kumar raja rajkumar.cs...@gmail.comwrote: @shady : i am not sure , if u can do it with O(n) space as well it is fine for me . but once try whether it is possible in O(1) space. On 24 November 2011 05:42, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: Finding the repeated element
Finding duplicates in a multiset is a pretty standard problem. I've only ever heard of two solutions, and it's unlikely there are others. One is to sort, which will place duplicates adjacent to each other, so you can find them by comparing a[i] with a[i+i] for all I. This algorithm is O(sorting time + scanning time), so O(n log n) using comparison sort, O(n) for counting sort, and O(n log k) for radix sort where k is magnitude of max element. Storage is O(1), O(k), and O(log k) respectively. The other is to use a set data structure, scan the input checking to see if the current element is already in the set (if so, it's a duplicate) and and then adding that element. This one is O(scanning time + n * lookup time + n * insert time). The most efficient set type is data dependent. For dense small integers, it's a bitmap. For arbitrary comparable keys it's either hash table or balanced tree depending on key type. Note that here the set insert and lookup depend not on n but on the number of _unique_ keys. If you have many repeats (think of a million 3's and 10 other numbers), this can have an impact. If you limit yourself to O(1) space, an in-place comparison sort and check of adjacent elements seems the best you can do: O(n log n). And the original data order is destroyed. If you must also maintain data order, O(n^2) all pairs comparison seems the best you can do. On Nov 24, 1:02 am, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Xor Linked lists
http://en.wikipedia.org/wiki/XOR_linked_list In this link i have seen about Xor linked list ,but my doubt is how will u perform xor on Address of nodes. I have tried to perform xor on addresses of two values ,so how is it possible to use that technique. Also tell me whether there are any extra rules to follow during insert,delete and search -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] Re: Finding the repeated element
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Xor Linked lists
address can be xored easily with xor operator... http://www.geeksforgeeks.org/archives/12367 On Thu, Nov 24, 2011 at 7:37 PM, kumar raja rajkumar.cs...@gmail.comwrote: http://en.wikipedia.org/wiki/XOR_linked_list In this link i have seen about Xor linked list ,but my doubt is how will u perform xor on Address of nodes. I have tried to perform xor on addresses of two values ,so how is it possible to use that technique. Also tell me whether there are any extra rules to follow during insert,delete and search -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Re: Finding the repeated element
@kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Xor Linked lists
go to link i said..n at bottom u can find sum programs that are user responshop it helps On Thu, Nov 24, 2011 at 8:45 PM, kumar raja rajkumar.cs...@gmail.comwrote: @rahul: when i tried the following i got an error int a=3,b=2; printf(%p, (a)^(b)); On 24 November 2011 06:28, rahul sharma rahul23111...@gmail.com wrote: address can be xored easily with xor operator... http://www.geeksforgeeks.org/archives/12367 On Thu, Nov 24, 2011 at 7:37 PM, kumar raja rajkumar.cs...@gmail.comwrote: http://en.wikipedia.org/wiki/XOR_linked_list In this link i have seen about Xor linked list ,but my doubt is how will u perform xor on Address of nodes. I have tried to perform xor on addresses of two values ,so how is it possible to use that technique. Also tell me whether there are any extra rules to follow during insert,delete and search -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Any one
Can you please elaborate... On Thu, Nov 24, 2011 at 12:14 AM, atul anand atul.87fri...@gmail.comwrote: yes levenshtein distance and BK tree can be used to solve this. where edge weight between nodes is equal to levenshtein distance. On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar afs.abhis...@gmail.comwrote: You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- Abhishek Kumar B.Tech(IT) Graduate Allahabad Contact no-+919663082731 -- 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.
Re: [algogeeks] Any one
http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees this would help. On Thu, Nov 24, 2011 at 9:49 PM, Vijay Meena vijay...@gmail.com wrote: Can you please elaborate... On Thu, Nov 24, 2011 at 12:14 AM, atul anand atul.87fri...@gmail.comwrote: yes levenshtein distance and BK tree can be used to solve this. where edge weight between nodes is equal to levenshtein distance. On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar afs.abhis...@gmail.comwrote: You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- Abhishek Kumar B.Tech(IT) Graduate Allahabad Contact no-+919663082731 -- 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.
Re: [algogeeks] Re: Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Struct tuple
{int s;int e;}
tuple findsubarray(Array input)
{
int i=0, j=input.length()-1;
while(input[i] input[i+1])
i++;
if(i==j) return NULL // array already sorted
while(input[j-1] input[j])
j--;
// now the subarrays from 0 to i is sorted and j to end is sorted.
int min = min(input(i+1,j-1));
int max = max(input(i+1,j-1));
while(input[i]min i0)
i--;
while(input[j]max jinput.size()-1)
j++;
return (i,j);
}
On Thu, Nov 24, 2011 at 6:09 PM, vikas vikas.rastogi2...@gmail.com wrote:
char arr[] = {'a', 'b', 'e', 'f', 'd', 'g', 'h', 'i'};
calculate the point where array is not sorted , in this case arr[4] =
'd'
calulate k in array[5..n] such that k 4 arr[k] d , take the min =
min{ arr[k] }
same thing for max from reverse
use quick /selection sort to identify the correct insertion indices of
min/max, that will be answer.
complexity O(n)
On Nov 24, 2:06 pm, Ankuj Gupta ankuj2...@gmail.com wrote:
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
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.
--
Nitin Garg
Personality can open doors, but only Character can keep them open
--
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.
Re: [algogeeks] Does Y lies between x and z
Please explain what do you mean by 'path between x and z'. On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.com wrote: There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
Re: [algogeeks] Re: An Array Problem
@Gene - nice, correct and elegant algorithm.
On Wed, Nov 23, 2011 at 9:33 PM, Ankur Garg ankurga...@gmail.com wrote:
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p=0, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it and
its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also
generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an
element,
it's too big to maintain the invariant, so it must be popped! We
can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is
O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder
techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the
right.
put the first element in stack.
take next element suppose num if this number is less than
elements
stored in stack, pop those elements , for these pooped
elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0
(valaue)
@techcoder : If the numbers are not in sorted order, What
benefit the
stack would provide ? So, are you storing the numbers in sorted
order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted
order.
Get
a new element from array and lets call this number as m. Push m
into the
stack. Now, find all elements which are = (m-1) using binary
search. Pop
out all these elements and assign the value m in the output array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage
ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta
ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
correspondence.
output[i] is equal to the input[j] (ji) which is smaller
than
input[i] and jth is nearest to ith ( i.e. first element which
is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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
[algogeeks] Re: Xor Linked lists
This is very language-dependent. In assembly it's no problem at all! In C you must coerce to an integer type where xor is possible. The portable way to make this work including 64-bit systems is to use type uintptr_t from stdint.h. Not all compilers have this. Perhaps the next best hing to try is size_t, which is declated in stdlib.h . However this is not guarenteed to be big enough. It will probably work on most systems however. So you'd compute the xor of two pointers p and q with: size_t xored_pointers = (size_t)p ^ (size_t)q; On Nov 24, 3:07 pm, kumar raja rajkumar.cs...@gmail.com wrote: http://en.wikipedia.org/wiki/XOR_linked_list In this link i have seen about Xor linked list ,but my doubt is how will u perform xor on Address of nodes. I have tried to perform xor on addresses of two values ,so how is it possible to use that technique. Also tell me whether there are any extra rules to follow during insert,delete and search -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
[algogeeks] structure padding query
struct abc
{
int g;
float f;
double gj;
};
like in this int takes 4 bytes and we want align in 8 bytes so i wana know
that whether the float should put with int as 4 bytes are there to complete
8 or float should be int+4 bytes padding and then store the float..
acc to o/p float is stores after int
--
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.
Re: [algogeeks] Re: Finding the repeated element
@kunzmilan Nice idea, how do you decide the row-size or column-size of the matrix? On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote: @kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Anup Ghatage -- 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.
Re: [algogeeks] Does Y lies between x and z
As it seems to me this can be solved like this Find LCA(Least common ancestor) of node x and z .. See if it equals y or not . If not recursively search for y in left and right subtree of LCA ..If you find y in the descendents of LCA answer is true else its false . This method will give perfect answer just that complexity would be a bit large (greater than n) but space wll be O(1) neglecting stack space during recursive calls I coded the same and it works to me .. If anyone can suggest a finer approach that wud be great :) Regards Ankur On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Please explain what do you mean by 'path between x and z'. On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.com wrote: There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
Re: [algogeeks] Re: Finding the repeated element
@Anup: Atleast u tell me how the M has formed??? On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote: @kunzmilan Nice idea, how do you decide the row-size or column-size of the matrix? On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote: @kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Anup Ghatage -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Does Y lies between x and z
This approach would fail in certain cases :P..in fact lot many cases :D..It needs to be modified using space The thing is while calculating LCA we must also store the path in an Array or vector and then Iterate over its elements to check if match occurs. Cant think of O(1) solution though :( On Fri, Nov 25, 2011 at 12:57 AM, Ankur Garg ankurga...@gmail.com wrote: As it seems to me this can be solved like this Find LCA(Least common ancestor) of node x and z .. See if it equals y or not . If not recursively search for y in left and right subtree of LCA ..If you find y in the descendents of LCA answer is true else its false . This method will give perfect answer just that complexity would be a bit large (greater than n) but space wll be O(1) neglecting stack space during recursive calls I coded the same and it works to me .. If anyone can suggest a finer approach that wud be great :) Regards Ankur On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Please explain what do you mean by 'path between x and z'. On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.comwrote: There is a binary tree (Not a BST) in which you are given three nodes X,Y, and Z .Write a function which finds whether y lies in the path b/ w x and z. -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
Re: [algogeeks] Re: Finding the repeated element
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements of the
array . This wud give us the repeating element as all the elements coming
once will be 0(xored twice) and repeating element wud be xored twice .
To code it as follows
int FindSingle(int a[],int n){
setints;
s.insert(a,a+n);
setint::iterator it;
it = s.begin();
int XOR= *it;
it++;
while(it!=s.end()){
XOR =XOR^*it;
it++;
}
for(int i=0;in;i++)
XOR=XOR^a[i];
return XOR;
}
On Fri, Nov 25, 2011 at 1:03 AM, kumar raja rajkumar.cs...@gmail.comwrote:
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it...
On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal are numbers of repeated elements.
kunzmilan
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except one
element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find All the
repeated
elements in an array in O(n) time and O(1) space
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
Write the list in the form of a matrix M, e.g.
0 1 0 0...
0 0 1 0...
0 0 0 1...
..etc.,
and its quadratic form M(T)M shows, how many times each element
repeats.
kunzmilan
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Anup Ghatage
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
Re: [algogeeks] Re: array searching
I don't think it can be done in better than O(n) space and time. On Tue, Nov 22, 2011 at 9:28 PM, himanshu kansal himanshukansal...@gmail.com wrote: @SAM: in your first step, where you are xoring the unique elements, you must be using some DS such as hashtable or something. so space complexity will be O(n). can someone reduces this O(n) space complexity.because it wont be a good approach if there are many elements in the array On Fri, Nov 18, 2011 at 9:26 AM, SAMM somnath.nit...@gmail.com wrote: On 11/18/11, SAMM somnath.nit...@gmail.com wrote: For example the array has .. 1 4 2 6 7 4 8 3.. xor the elements in the array will give (1^2^6^7^8^3). now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3). Now xor these two value which gives 4. On 11/18/11, Dave dave_and_da...@juno.com wrote: @SAMM: It sounds like a circular argument. How do you XOR all of the unique elements without first finding the repeated ones? Dave On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote: Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice. Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal himanshukansal...@gmail.com wrote: consider an array having n elements.out of which one number is repeated twiceother number are repeated odd number of times(for simplicity, assume other numbers are occurring just once) can you find the number that is repeated twice in O(n) time??? PS: numbers are not from a particular range. -- 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. -- Somnath Singh -- 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. -- Somnath Singh -- Somnath Singh -- 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. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
Re: [algogeeks] Re: An Array Problem
@Gene : Are you sure, when you pop element from stack it will not be next
smaller element to remaining elements in the array(Input)?? I think this is
not gonna work...
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov 23, 6:59 am, Gene gene.ress...@gmail.com wrote:
Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
doesn't mention anything about pairs, which are necessary to obtain
O(n). This is what I meant by almost.
In reverse order, you don't need the pairs. Its simpler.
In a subroutine like yours,
void find_smaller_to_right(int *a, int n)
{
int i, in, p=0, stk[n]; // C99 var length array
for (i = n - 1; i = 0; i--) {
in = a[i];
while (p 0 stk[p - 1] = in) p--; // pop
a[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in; // push
}
}
On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote:
Solution given by tech coder is fine and is working .. I coded it
and its
working perfectly using stack
On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com
wrote:
It's a nice problem, and this solution is almost right.
Process the input in _reverse_ order, which means we'll also
generate
output in reverse order.
The invariant is that the stack is a sorted list - highest value on
top - of the strictly descending subsequence of elements seen so
far
in reverse.
So when we get a new input, we want to search backward through the
stack to find the first smaller element. This is handy however,
because the new input also means that when we search past an
element,
it's too big to maintain the invariant, so it must be popped! We
can
both find the output value and update the stack at the same time:
stack = empty
for next input I in _reverse order_
while stack not empty and top of stack is = I
pop and throw away top of stack
if stack is empty, output is zero
else output top of stack
push I
end
Since each item is pushed and popped no more than once, this is
O(n).
Here's your example:
#include stdio.h
int main(void)
{
int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
int n = sizeof in / sizeof *in - 1;
int out[100], stk[100], p = 0, i;
for (i = n - 1; i = 0; i--) {
while (p stk[p - 1] = in[i]) p--;
out[i] = (p 0) ? stk[p - 1] : 0;
stk[p++] = in[i];
}
for (i = 0; i n; i++) printf( %d, out[i]);
printf(\n);
return 0;
}
On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov 22, 2011 at 11:50 PM, tech coder
techcoderonw...@gmail.com
wrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the
right.
put the first element in stack.
take next element suppose num if this number is less than
elements
stored in stack, pop those elements , for these pooped
elements num
will
be the required number.
put the the element (num) in stack.
repeat this.
at last the elements which are in next , they will have 0
(valaue)
@techcoder : If the numbers are not in sorted order, What
benefit the
stack would provide ? So, are you storing the numbers in sorted
order
inside the stack ?
I can think of this solution :
Maintain a stack in which the elements will be stored in sorted
order.
Get
a new element from array and lets call this number as m. Push m
into the
stack. Now, find all elements which are = (m-1) using binary
search. Pop
out all these elements and assign the value m in the output
array.
Elements
remaining at the end will have the value 0.
I am not sure about the complexity of this algorithm...
On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage
ghat...@gmail.com
wrote:
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta
ankuj2...@gmail.com
wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
correspondence.
output[i] is equal to the input[j] (ji) which is smaller
than
input[i] and jth is nearest to ith ( i.e. first element
which is
smaller).
If no such element exists for Input[i] then output[i]=0.
Eg.
Input: 1 5 7 6 3 16 29 2 7
Output: 0 3 6 3 2 2 2 0 0
--
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
