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.
