Ineffecient algorithm of finding the sum of even numbers after queries

rockzxm 0
Viewed 95

I decided to complete some tasks on Leetcode to improve my algorithm skills.
And I ran into a problem with LeetCode's problem 985. Sum of Even Numbers After Queries

Here is the description of that task:

You are given an integer array nums and an array queries where queries[i] = [valᵢ, indexᵢ].
For each query i, first, apply nums[indexᵢ] = nums[indexᵢ] + valᵢ, then print the sum of the even values of nums.
Return an integer array answer where answer[i] is the answer to the ith query.

Some samples of input and output:

# input1: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
# output1: [8, 6, 2, 4]

# input2: nums = [1], queries = [[4,0]]
# output2: [0]

So I found the solution, but as it has some huge samples of inputs, I found that my code is not efficient enough.

Here is my code:


class Solution:
    def sumEvenAfterQueries(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        ans = []
        integer_ans = 0
        
        for i in range(len(queries)):
            nums[queries[i][1]] = nums[queries[i][1]] + queries[i][0]
            for j in nums:
                if j % 2 == 0:
                    integer_ans += j
            ans.append(integer_ans)
            integer_ans = 0
        return ans

So it does not solve problem because of the Time limit exceeded.

How can I improve my code to make it more efficient?

python-3.x algorithm python
3 Answers

Try this solution. This will initially build up even_nums which are sum of even numbers in list, then incrementally update it with each value in queries.

It's probably not the most efficient, but it works for me. I submit on leetcode just now.

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        even_sum = sum(x for x in nums if not x % 2)

        result = []
        for (add, i) in queries:
            n = nums[i]
            if add % 2:  # odd
                if n % 2:  # both odd, result is even
                    even_sum += n + add
                else:  # even, add odd, result is odd
                    even_sum -= n
            # odd, add even, result is still odd
            # so, both must be even
            elif not n % 2:  # both even
                even_sum += add
            # remember updating nums at index @i
            # and then adding to ours result
            nums[i] = n + add
            result.append(even_sum)

        return result
rv.kvetch0

Not so optimised solution, but you need to keep update of the sum of even values first and then for every query you run, you need to make the changes for the index of that value and see if sum for that index is calcualed or not. if not then add it to total sum and update the nums and if it is calculate then add the new sum value to it and modify the nums accordingly.

below is a simple way to achive this.

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        dic = {i:v for i, v in enumerate(nums) if v%2==0}
        sum_ = sum(dic.values())
        res = []
        for v, i in queries:
            val = nums[i]
            new_val = nums[i] + v
            if i not in dic:
                if new_val%2==0:
                    dic[i] = new_val
                    sum_ += new_val
                    res.append(sum_)
                else:
                    res.append(sum_)
            else:
                if new_val%2==0:
                    sum_ -= val
                    sum_ += new_val
                    dic[i] = new_val
                    res.append(sum_)
                else:
                    sum_-= val
                    del dic[i]
                    res.append(sum_)
            nums[i] = new_val            
        return res
sahasrara620

This is an addition to rv.kvetch answer
Your code is giving TLE because it has the worst case time complexity of O(n2). I hope you know about the it.
Coming to the solution, we can do in in O(n) i.e. linear time.

Algorithm

  1. Initially we will store sum of all even numbers present in nums to all_sum
  2. Adding value to any item of nums list can make nums[index] + value even or odd, we will check these conditions
  3. Based on these conditions checks, we either add (value or nums[index] + value) or subtract nums[index] from all_sum
  4. After all these condition checks we will modify nums[index] to be nums[index] = nums[index] + value and add all_sum to the array that we want to return as answer

Code

def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        all_sum = 0
        for e in nums:
            if e%2 == 0:
                all_sum += e
        
        sum_arr = []
        for val, index in queries:
            if nums[index] % 2 == 0: # nums item is already added to all_sum
                if (nums[index] + val) % 2 == 0: 
                    all_sum += val
                else:
                    all_sum -= nums[index]
            else: # nums item is odd so it wasn't added to all_sum before
                if (nums[index] + val) % 2 == 0:
                    all_sum += (nums[index] + val)
                else:
                    pass
            nums[index] += val
            sum_arr.append(all_sum)
        return sum_arr
Mr. Techie0
Related