Sum of Even Numbers After Queries
Sum of Even Numbers After Queries
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
- Different languages may produce different results when performing modulo operations on negative numbers.