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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
