Sub-array Factor

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous sub-array of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

The Idea: First accumulate the array to built discrete function F(x). Then F(b) - F(a) will return the subsequent sum between a and b where a <= b, and a and b are indices in the array. Avoid duplicate sub-sequences as well as sub-sequences that are less than length 2 by setting j = i + 1. For all real numbers n>0, multiples of k*n can be found when sub_sum % k == 0.

Complexity: O(n^2) time and O(n) space where n is the length of the array.

bool has_factor_k_subarray(const vector<int> &ar, const int k) {
    // modify to accumulative array
    vector<int> cum_sum(ar.size());
    partial_sum(ar.begin(), ar.end(), cum_sum.begin());
    for (int i = 0; i < ar.size(); i++) {
        for (int j = i + 1; j < ar.size(); j++) {
            int sub_seq_sum = (ar[j] - ar[i]);
            if (sub_seq_sum >= k && sub_seq_sum % k == 0)
                return true;
        }
    }
    return false;
}


int main()
{
    vector<int> ar = {0,1,2,3,4,5,6,7,6,7};
    cout << has_factor_k_subarray(ar, 2) << endl;
    cout << has_factor_k_subarray(ar, 1000) << endl;
}