Sum of Even Numbers After Queries

My first solution to this easy problem passed but only faster than 6% of submissions which means we still have some room for improvements.

class Solution {
    fun sumEvenAfterQueries(A: IntArray, queries: Array<IntArray>): IntArray {
        var answer = IntArray(queries.size)
        var currentSum = A.map { if(it % 2 == 0) it else 0 }.sum()
        
        for(x in 0 until queries.size){
            val query = queries[x]
            val oldValue = A[query[1]]
            A[query[1]] += query[0]
            
            when {
               A[query[1]] % 2 == 0 -> {
                   when {
                      oldValue % 2 == 0 -> currentSum += query[0]
                      else -> currentSum += A[query[1]]                
                   }
               }
               
               oldValue % 2 == 0 -> currentSum -= oldValue
            }
                        
            answer[x] = currentSum            
        }
        
        return answer
    }
}
Runtime: 404 ms, faster than 43.75% of Kotlin online submissions for Sum of Even Numbers After Queries.
Memory Usage: 56.9 MB, less than 100.00% of Kotlin online submissions for Sum of Even Numbers After Queries.

The first version looks similar except that for every loop in for-loop, we also loop through the array A to get the sum of the even values. I realized that we can just precompute the sum of even values of A and then maintain a running variable which holds the current sum of even values. Based on the previous and currently modified value of A[index], we can decide whether we need to increment the current sum or decrement it.

In this way, we don’t have to perform two loops thereby improving the performance.

comments powered by Disqus