Codechef: Remove pairwise common factors from array elements and find minimum product. Why Wrong Answer?

Question

Problem Statement: You are given a array A of N positive integers, and you can perform the following operation on the array
1) Pick any two indices i and j in the array (i != j)
2) Divide A[i] and A[j] by some common factor of A[i] and A[j]

You can perform the above operation as many number of times as you want, and the aim is to minimize the product of the resulting array. Find this minimum product. Since the answer can be a large number, print the product modulo 1000000007.

INPUT:

First line contains T, number of testcases. Each testcase contains 2 lines. First line of each testcase contains single integer N, size of the array.

Second line of each testcase contains N space separated integers, the array A

OUTPUT:
For each testcase, output single line indicating the answer to that testcase

CONSTRAINTS:

1<=T<=10  
30 points : 1<=N<=2000, 1<=A[i]<=10^6  
70 points : 1<=N<=20000, 1<=A[i]<=10^8

SAMPLE INPUT:  
1  
3  
2 3 6  

SAMPLE OUTPUT:
1

My Code:

#include <iostream>
#include <vector>

using namespace std;


// Take two elements of vector by reference. Then divide them by their common factors.
void common(unsigned long long int &sm, unsigned long long int &big)
{
    while (sm%2 == 0 && big%2 == 0)
    {
        sm /= 2;
        big /= 2;
    }

    for (unsigned long long int i = 3; i <= big && i <= sm; i = i+2)
    {
        while (sm%i == 0 && big%i == 0)
        {
            sm /= i;
            big /= i;
        }
    }
}


int main()
{
  long long int T, N;
  vector<unsigned long long int> v(20000);
  unsigned long long int prod = 1;
  cin >> T;
  while ( T-- )
  {
    cin >> N;
    for ( long long int i = 0;i < N; i++ )
       cin >> v[i];

    for ( long long int i = 0; i < N; i++ )
       for ( long long int j = i+1; j < N; j++ )
       {
          if (v[j] >= v[i] && v[j] % v[i] == 0) {
             v[j] /= v[i];
             v[i] = 1;
             break;
          }
          if (v[i] > v[j] && v[i] % v[j] == 0) {
             v[i] /= v[j];
             v[j] = 1;
             continue;
          }
          common( v[i], v[j] );
       }

     prod = 1;
     for ( long long int i = 0; i < N; i++ )
        prod = (prod * v[i]) % 1000000007;

     cout << prod << endl;
  }
  return 0;
}

I understand the solution given by the problem setters. It is to find the prime factors of each of the elements and then eliminate them in an efficient manner.

But what I am not clear about is why my algorithm is not working and where is the error. Unfortunately the test cases are not public, otherwise I could have debugged the code myself.

Can anyone please help me spot it?

Thanks!

Answer 1

It is wrong because you must find the minimum product of your array. With you code, you don't search to minimize this product, you just divide integers when it is possible.

Consider the following example:

1
5
1 3 6 9 2

The output must be 1. With your code, it is 9. Why ? Because you take as pair 3 and 6, and get 1 1 2 9 2. But if you get the pair 3 and 9, you get 1 1 6 3 2... And then you can have 1 1 2 1 2.