Print the sum of array after doing k queries on the array

By Ann Roberts On Dec 29, 2022

Given an array, arr[] of size n. Calculate the sum of arr[] by performing k queries on arr[], such that we have to add an element given in array y[], on the basis of the boolean value given in array check[].

For every index i (0<= i <= n – 1):

If check[i] = true, Add y[i] to all the odd numbers present in the array.
If check[i] = false, Add y[i] to all the even numbers present in the array.

Examples:

Input: n = 3, k = 3, arr[] = {1, 2, 4}, check[] = {false, true, false}, y[] = {2, 3, 5}
Output: 29
Explanation:

for, k = 1
check[0] = false, y[0] = 2
So, as per operation add to the even number
arr = [1, 2+2, 4+2] = {1, 4, 6}

for, k = 2
check[1] = true, y[1] = 3
so, add to the odd number
arr = [1+3, 4, 6] = {4, 4, 6}

for, k = 3
check[2] = false, y[2] = 5
so, add to the even number
arr = [4+5, 4+5, 6+5] = {9, 9, 11}

So, finally, print the sum of the array = 9 + 9 + 11 = 29

Input: n = 2, k = 1, arr[] = {1, 2}, check[] = {false}, y[] = {0}
Output: 3
Explanation: As check[0] = false, we have to y[0] to all the even elements present in the array. Therefore, the final sum is 1 + 2 =3.

Approach: The basic idea to solve the above problem is:

Iterate through whole the array arr[] for k times, check whether the element present is odd or even, and add an element accordingly.

Time complexity: O(k*n), where k = no of queries , n = length of array
Auxiliary Space: O(1)

Efficient Approach: The above idea can be optimized as:

Iterate over the arr[], count the number of even and odd elements present. Now, Run a loop for k queries along by keep a check on array check[]. If check[i] == true, Add the total sum by count odd * y[i], otherwise if it’s false, add count even * y[i]. Also, change the count of even and odd according to y[i], if it’s odd.

Steps involved in the implementation of the code:

Step 1: First calculate the total sum of the array.

Step 2: count of number of odd and even elements in the array.

Step 3: Run the loop for the k queries.

Step 4: If (check[first loop index] = true) then,

Update the total sum => total sum += (count odd * y[first loop index])

If the number which is added y[first loop index] is odd then,

Update even count => count even += odd count, and odd count = 0

Step 5: If(check[first loop index] = false) then,

Update the total sum => total sum += (count even* y[first loop index])

If the number which is added y[first loop index] is odd then,

Update odd count => odd count += even count, and even count = 0

Step 6: Finally print the total sum.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to calculate the final sum
long long sum(int n, int k, vector<int> arr,
              vector<bool> check, vector<int> y)
{
    // It will store the final answer
    long long totalSum = 0;

    int countOdd = 0, countEven = 0;

    // Loop for finding the totalSum
    // and count odd and even
    for (int i = 0; i < n; i++) {
        totalSum = totalSum + arr[i];
        if (arr[i] & 1)
            countOdd++;
        else
            countEven++;
    }

    // Loop for k queries
    for (int q = 0; q < k; q++) {

        if (check[q]) {
            // Adding to odd number
            totalSum = totalSum + (countOdd * 1LL * y[q]);

            if (y[q] & 1) {
                countEven = countEven + countOdd;
                countOdd = 0;
            }
        }
        else {
            // Adding to even number
            totalSum = totalSum + (countEven * 1LL * y[q]);

            if (y[q] & 1) {
                countOdd = countOdd + countEven;
                countEven = 0;
            }
        }
    }
    // Returning the final answer
    return totalSum;
}

// Driver code
int main()
{

    // Input 1
    int n1 = 3, k1 = 3;
    vector<int> arr1 = { 1, 2, 4 };
    vector<bool> check1 = { false, true, false };
    vector<int> y1 = { 2, 3, 5 };

    // Function call
    cout << sum(n1, k1, arr1, check1, y1) << endl;

    // Input 2
    int n2 = 6, k2 = 7;
    vector<int> arr2 = { 1, 3, 2, 4, 10, 48 };
    vector<bool> check2
        = { true, false, false, false, true, false, false };
    vector<int> y2 = { 6, 5, 4, 5, 3, 12, 1 };

    // Function call
    cout << sum(n2, k2, arr2, check2, y2) << endl;
    return 0;
}

Time Complexity: O(max(n, k)), where n = size of array, k = no of queries
Auxiliary Space: O(1)