1
$\begingroup$

Here is the question: Link. In a gist, we need to count the total count of numbers that would divide every number in an array.

The approach that I took was that any number that has to divide all the numbers must be less than or equal to the smallest number in the array. For e.g., if the array is [6 90 12 18 30 18] - any divisor cannot be greater than 6, because that would not divide 6.

Based on above logic, here's the code that I wrote:

#include <bits/stdc++.h>

using namespace std;

//output
#define output(x) cout << x << endl
#define ll long long

int main(int argc, char const *argv[])
{ 
    int n;
    cin >> n;

    vector<ll> v(n);

    ll smallest = LONG_MAX;
    for (auto &it: v) {
        cin >> it;

        if (it < smallest) {
            smallest = it;
        }
    }

    set<ll> divisors;

    for (ll i = 1; i*i <= smallest; i++) {
        if (smallest%i == 0) {
            ll q = smallest/i;
            divisors.insert(i);
            divisors.insert(q);
        }
    }


    for (auto &it: v) {
        vector<ll> removeEl;

        for (auto &div: divisors) {
            if (it%div != 0) {
                removeEl.push_back(div);
            }
        }

        for (auto &rem: removeEl) {
            divisors.erase(rem);
        }
    }

    output(divisors.size());


    return 0;
}

This fails [wrong answer] on some test case - is there something incorrect in my implementation or my approach to the question?

$\endgroup$
  • $\begingroup$ is it a set, so it cannot. $\endgroup$ – prabodhprakash May 28 at 18:57
  • $\begingroup$ What is the test case it failed (like input, output and expected output)? $\endgroup$ – nir shahar May 28 at 19:11
  • $\begingroup$ Not entirely coming on codeforces, it is too big. $\endgroup$ – prabodhprakash May 28 at 19:34
  • 1
    $\begingroup$ Basically, the minimum that I have taken is LONG_MAX - while, in the question, the data in the array can go upto 10^12, hence, in the case where it failed, LONG_MAX was the minimum and hence the algorithm was incorrectly working. Nothing else is wrong here.a $\endgroup$ – prabodhprakash May 28 at 19:42
  • $\begingroup$ Confirmed, smallest should be initialized to LONG_LONG_MAX since, on current Codeforces.com, LONG_MAX=2147483647 while LONG_LONG_MAX=9223372036854775807. #include<iostream> #include<climits> int main() { std::cout << LONG_MAX << std::endl << LONG_LONG_MAX << std::endl; } at codeforces.com/problemset/customtest . $\endgroup$ – John L. May 28 at 20:32

Browse other questions tagged or ask your own question.