SUMAGCD C++ Errors

help
1

Below is my attempt at solving SUMAGCD using CPP -

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll getGCD(ll a, ll b){
    if(a%b == 0){
        return b;
    }else{
        getGCD(b,a%b);
    }
}

int main(){
    ll t,n,temp;

    cin >> t;

    for(ll i=0; i<t; i++){
        cin >> n;
        set<ll> nums = {};

        for(ll j=0; j<n; j++){
            cin >> temp;
            nums.insert(temp);
        }

        vector<ll> prefix = {};
        vector<ll> suffix = {};

        prefix.push_back(*nums.begin());
        suffix.push_back(*nums.rbegin());

        for(set<ll>::iterator it=++nums.begin(); it != nums.end(); it++){
            temp = getGCD(prefix.back(), *it);
            prefix.push_back(temp);
        }

        for(set<ll>::reverse_iterator it = ++nums.rbegin() ; it != nums.rend(); it++){
            temp = getGCD(suffix.back(), *it);
            suffix.push_back(temp);
        }

        ll ans = 1;
        ll index = 0;

        for(set<ll>::iterator it = nums.begin(); it != nums.end(); it++){
            if(index == 0){
                ans = max(suffix[n-2] + *it, ans);
            }
            else if(index == n-1){
                ans = max(prefix[n-2] + *it, ans);
            }
            else{
                ans = max(getGCD(prefix[index-1], suffix[n-1-index-1]) + *it, ans);
            
            }

            index++;
        }

        cout << ans << endl;
    }

    return 0;
}

Please can someone help me debug my code?
CPP Submission

2

The problem is in the loop at line 46. You want to access the second last elements of suffix and prefix vectors but instead you are accessing suffix[n-2]. The length of suffix and prefix is the same as length of nums which is equal to the number of distinct elements in the array which is not equal to n if the array contains duplicates. Just change n in that loop to nums.size() 1. However that will still give WA verdict because if there is only one distinct element, your code will try to access the second last element in suffix ( which doesn’t exist ) and will give a random garbage value. Final AC Solution

1 Like
3

Thanks a lot!
That was a silly error