Sum of Even Numbers After Queries

Sum of Even Numbers After Queries

Problem Description

Time complexity: O(N) Space complexity: O(1)

// Author: Tecker
// 176ms, 28.7MB; beat 96.40%, 100%
class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int> >& queries) {
        vector<int> res(A.size(), 0);
        int sum=0;
        A[queries[0][1]]+=queries[0][0];
        for(int &num : A) {
            if (num%2==0) sum+=num;
        }
        res[0]=sum;
        for(int i=1;i<queries.size();++i) {
            int val=queries[i][0];
            int idx=queries[i][1];
            int tmp = A[idx];
            A[idx]+=val;
            if (isEven(tmp)) {
                if (!isEven(A[idx]))
                    sum-=tmp;
                else
                    sum+=val;
            } else {
                if (isEven(A[idx])) sum+=A[idx];
            }
            res[i]=sum;
        }
        return res;
    }
    
private:
    inline bool isEven(int a) {
        return !(a & 1);
    }
};

I started out thinking I could use modulo operations, but I accidentally fell into a big trap. I need to pay attention to the correct way to calculate modulo with negative numbers.

int mod(int x, int m) {
    return (x%m + m)%m;
}

Lessons

  1. Different languages may produce different results when performing modulo operations on negative numbers.