No it's not O(n). Coz you're scanning the array and in case you do not find a solution, you're jumping back to the start of the loop. That's equivalent to a nested loop. And I think in the worst case...it'll turn out to be an O(n^2) solution. Please correct me if I'm wrong.
On Fri, Jul 13, 2012 at 8:29 PM, jatin <jatinseth...@gmail.com> wrote: > as long as we are using goto with proper comments to ensure that it won't > decrease the readability we can use them and ther's no harm in it! > Secondly the worst case for my algo is o(n) .?..correct me if i am wrong > > On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote: > >> Ya I didn't see that part, sorry. And in general, using goto is not >> advisable. >> Plus this will exceed O(n) in the worst case, as we may keep visiting the >> goto again and again. Not sure of its exact time complexity. >> ------------------------------ >> From: vindhya chhabra >> Sent: 13-07-2012 17:46 >> To: algogeeks@googlegroups.com >> Subject: Re: [algogeeks] Re: Amazon Interview Question >> >> @adarsh >> But i think jatin has asked to check for the number( we achieved in step >> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt >> the algo given by Jatin runs in O(n) time. please comment. >> >> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar <algog...@gmail.com> wrote: >> >>> @jatin: >>> Your first method may be proved wrong. >>> >>> Here is a counter test case: >>> >>> Suppose the array is: >>> >>> 27 729 19683 2 3 3 27 3 81 729 >>> >>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice, >>> 27 occurs twice, and 3 occurs thrice. >>> >>> You are supposed to return 3 >>> But as per your method, the product will be computed as >>> 729*19683*2*3*3*27*3*81*729=**product(say) >>> >>> Upon traversing the second time, it will return 27, as >>> product%(27*27*27) is equal to zero! >>> >>> regards. >>> >>> >>> >>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin <jatinseth...@gmail.com> wrote: >>> >>>> Or we can make a BST from array list in ----o(n) >>>> then traverse it inorder-----o(logn) >>>> >>>> but this solution requires o(logn) space though. >>>> >>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote: >>>> >>>>> >>>>> 1)Find product of the array and store it in say prod ---- o(n) and >>>>> o(1) >>>>> 2)now traverse the array and check if >>>>> >>>>> static int i; >>>>> tag: >>>>> while(i<n) >>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0) >>>>> break; >>>>> //this may be the required element >>>>> //e-o-while >>>>> >>>>> //now check is this is the element that is occuring three times >>>>> ----o(n) >>>>> if(number is not the required one then) >>>>> goto tag; >>>>> >>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: >>>>> >>>>>> Given an array of integers where some numbers repeat once, some >>>>>> numbers repeat twice and only one number repeats thrice, how do you find >>>>>> the number that gets repeated 3 times? >>>>>> >>>>>> Does this problem have an O(n) time and O(1) space solution? >>>>>> No hashmaps please! >>>>>> >>>>> -- >>>> 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/-/lmzhJ-GSdigJ<https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ>. >>>> >>>> >>>> To post to this group, send email to algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/algogeeks?hl=en <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+unsubscribe@** >>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >>> For more options, visit this group at http://groups.google.com/** >>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>> >> >> >> >> -- >> Vindhya Chhabra >> >> >> >> -- >> 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+unsubscribe@** >> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>. >> For more options, visit this group at http://groups.google.com/** >> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >> > -- > 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/-/wYWXoPmf9_MJ. > > 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.
