@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. >> >> 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. > -- 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+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
