Problem : link text I began by first primefactorizing each number of the array. Given one goodpair (ik,jk) we can divide both numbers A[ik] and A[jk] by their common prime powers i.e if A[ik]=2^5 * 3^4 and A[jk]=2^3 * 3^7 then we can divid both of them by 2 a total of 3 times and divide by 3 a total number of 4 times. The number of operations increase by the minimum of the common prime powers i.e by 7. Total number of operations can then be taken as the sum over all common prime powers for all good pair given. Here is my approach. My code : link text Pretest 5 contains this test data. My answer on this is 28 but the correct answer is 31. Can anyone explain why the output is 31 and the correct approach to solve the problem? 10 9 67108864 8 2 131072 268435456 256 16384 128 8 128 4 9 5 10 6 9 9 10 1 4 3 8 8 9 1 2 4 5 asked 25 Dec '14, 18:02

The problem is that you are doing is greedily, which is wrong approach. Try this test case :
Your code is giving 3 as output, while the correct output should be 5. If we change the order of the input it gives correct answer. Hope it helps!! Happy Coding!!! answered 25 Dec '14, 22:45
