[algogeeks] Sorting in O(n)
How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. 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] Code optimization.
Are you summing the numbers on each set query? Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Fri, May 4, 2012 at 10:56 PM, vIGNESH v v.v.07121...@gmail.com wrote: Hai Can you brief about the rest of the cases? On 4 May 2012 01:56, Umer Farooq the.um...@gmail.com wrote: Hi friends! I hope that you are doing really good these days. I submitted my code on interviewstreet.com The problem statement can be found on https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c739a6ea3a However, it passed for only two cases and gave a time out error for the rest of cases. Can anyone please tell me where I am lacking? Is there anything I can do to improve the running time of my code? I thought it was because Java runs slower, but they have a greater limit of running time for java code. Please find the code in the attachment. -- Umer -- 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] Sorting in O(n)
The range 1 to n^2 is already sorted On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. 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] Code optimization.
They haven't shared the rest of test cases. However, the execution time difference is extremely high. It took about 0.3 and 0.6 sec for the cases in which it executed successfully. However, it was taking more than 5 sec on test cases in which it couldn't run. On Fri, May 4, 2012 at 10:26 PM, vIGNESH v v.v.07121...@gmail.com wrote: Hai Can you brief about the rest of the cases? On 4 May 2012 01:56, Umer Farooq the.um...@gmail.com wrote: Hi friends! I hope that you are doing really good these days. I submitted my code on interviewstreet.com The problem statement can be found on https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c739a6ea3a However, it passed for only two cases and gave a time out error for the rest of cases. Can anyone please tell me where I am lacking? Is there anything I can do to improve the running time of my code? I thought it was because Java runs slower, but they have a greater limit of running time for java code. Please find the code in the attachment. -- Umer -- 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. -- Umer -- 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: Sorting in O(n)
You can use Radix Sort. It will have a Time Complexity of O(n). On Saturday, May 5, 2012 12:17:15 AM UTC+5:30, Algobiz wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OLTTwzx8f9MJ. 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] Sorting in O(n)
@cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily sorted. eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 5:17 AM, Prakash D cegprak...@gmail.com wrote: The range 1 to n^2 is already sorted On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. 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] Code optimization.
I meant what is your algorithm, are you summing up the entire numbers A and B every time a set query is made? Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Fri, May 4, 2012 at 11:32 PM, Umer Farooq the.um...@gmail.com wrote: They haven't shared the rest of test cases. However, the execution time difference is extremely high. It took about 0.3 and 0.6 sec for the cases in which it executed successfully. However, it was taking more than 5 sec on test cases in which it couldn't run. On Fri, May 4, 2012 at 10:26 PM, vIGNESH v v.v.07121...@gmail.com wrote: Hai Can you brief about the rest of the cases? On 4 May 2012 01:56, Umer Farooq the.um...@gmail.com wrote: Hi friends! I hope that you are doing really good these days. I submitted my code on interviewstreet.com The problem statement can be found on https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c739a6ea3a However, it passed for only two cases and gave a time out error for the rest of cases. Can anyone please tell me where I am lacking? Is there anything I can do to improve the running time of my code? I thought it was because Java runs slower, but they have a greater limit of running time for java code. Please find the code in the attachment. -- Umer -- 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. -- Umer -- 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] Code optimization.
Nevermind i read your code. Your algorithm is wrong. what you are doing here is adding up the complete binary numbers A and B every time a query is made. Instead use something like a bitvector for java to store the two binary numbers and another bit vector to store C, and another to store the carry forwards let it be X. Initially sum both the numbers according to your method and save C and the carry array X. Now when a set query is made. let it be seta 3 1. So you need to consider only three or four cases at max. the lower bits in the summation will not change. Now set A[3] to 1 and just compute C[3] = A[3] + B[3] + X[3]; if the sum is greater than 2. check X[4] if it's is 0 set X[4] to 1 and compute C[4] and so on. Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Sat, May 5, 2012 at 9:37 AM, Sukun Tarachandani sukun...@gmail.comwrote: I meant what is your algorithm, are you summing up the entire numbers A and B every time a set query is made? Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Fri, May 4, 2012 at 11:32 PM, Umer Farooq the.um...@gmail.com wrote: They haven't shared the rest of test cases. However, the execution time difference is extremely high. It took about 0.3 and 0.6 sec for the cases in which it executed successfully. However, it was taking more than 5 sec on test cases in which it couldn't run. On Fri, May 4, 2012 at 10:26 PM, vIGNESH v v.v.07121...@gmail.comwrote: Hai Can you brief about the rest of the cases? On 4 May 2012 01:56, Umer Farooq the.um...@gmail.com wrote: Hi friends! I hope that you are doing really good these days. I submitted my code on interviewstreet.com The problem statement can be found on https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c739a6ea3a However, it passed for only two cases and gave a time out error for the rest of cases. Can anyone please tell me where I am lacking? Is there anything I can do to improve the running time of my code? I thought it was because Java runs slower, but they have a greater limit of running time for java code. Please find the code in the attachment. -- Umer -- 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. -- Umer -- 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] Code optimization.
http://en.wikipedia.org/wiki/Bit_array Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Sat, May 5, 2012 at 9:49 AM, Sukun Tarachandani sukun...@gmail.comwrote: Nevermind i read your code. Your algorithm is wrong. what you are doing here is adding up the complete binary numbers A and B every time a query is made. Instead use something like a bitvector for java to store the two binary numbers and another bit vector to store C, and another to store the carry forwards let it be X. Initially sum both the numbers according to your method and save C and the carry array X. Now when a set query is made. let it be seta 3 1. So you need to consider only three or four cases at max. the lower bits in the summation will not change. Now set A[3] to 1 and just compute C[3] = A[3] + B[3] + X[3]; if the sum is greater than 2. check X[4] if it's is 0 set X[4] to 1 and compute C[4] and so on. Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Sat, May 5, 2012 at 9:37 AM, Sukun Tarachandani sukun...@gmail.comwrote: I meant what is your algorithm, are you summing up the entire numbers A and B every time a set query is made? Sukun Tarachandani IDD Electrical Engineering(2nd year) IIT Roorkee On Fri, May 4, 2012 at 11:32 PM, Umer Farooq the.um...@gmail.com wrote: They haven't shared the rest of test cases. However, the execution time difference is extremely high. It took about 0.3 and 0.6 sec for the cases in which it executed successfully. However, it was taking more than 5 sec on test cases in which it couldn't run. On Fri, May 4, 2012 at 10:26 PM, vIGNESH v v.v.07121...@gmail.comwrote: Hai Can you brief about the rest of the cases? On 4 May 2012 01:56, Umer Farooq the.um...@gmail.com wrote: Hi friends! I hope that you are doing really good these days. I submitted my code on interviewstreet.com The problem statement can be found on https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c739a6ea3a However, it passed for only two cases and gave a time out error for the rest of cases. Can anyone please tell me where I am lacking? Is there anything I can do to improve the running time of my code? I thought it was because Java runs slower, but they have a greater limit of running time for java code. Please find the code in the attachment. -- Umer -- 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. -- Umer -- 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.
