• + 0 comments

    O(n) solution in C++, two passes through the array.

    First pass, initialize a hashmap with the values mod the desired sum

    Second pass, remove the current element from the hashmap and find the subtractive complement frequency in the hashmap, add that to the result.

    Edge case: if the number mods to 0, we don't do any subtraction, we just want to know how many successive elements are also multiples of k. Also of note, we don't want to use the [] operator, since that will implicitly insert that mod into the hashmap with a freq of 0, so we use the count function.

    int divisibleSumPairs(int n, int k, vector<int> ar) {
        int result = 0;
        map <int, int> f;
        for (auto a : ar) f[a%k]++;
        for (auto a : ar) {
            f[a%k]--;
            if (a % k == 0)
                result += f.at (0);
            else
                result += f.count (k - a%k) ? f.at (k - a%k) : 0;
        }
        return result;
    }