use XOR
On Tue, Apr 30, 2013 at 6:12 AM, Gary Drocella <[email protected]> wrote: > This will only work if each element in the array are relatively prime to > one another, that is for any two elements x, y in array A the gcd(x,y) = 1, > which is also just another way of saying no number divides another number > in the array. Once this rule is broken, then > the algorithm will no longer work. Here is a counter example > > A = { 4,3,4,2,4,2 } = {2^2, 3, 2^2, 2, 2^2, 2} > > You might be able to see now why this algorithm breaks down. It is > because the final product = 2^8*3^1 and of course 2^3 will easily divide > this number, but would return the wrong solution. It was of course a very > good try! > > On Thursday, July 12, 2012 11:46:50 PM UTC-8, jatin 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 unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- regards Parag Khanna -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
