# 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.

```cpp
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;
}
```