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

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++ 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; } 

import java.util.*; class Main {  // Function to calculate the final sum  static long sum(int n, int k, int[] arr,  boolean[] check, int[] y)  {  // It will store the final answer  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) == 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 * 1L * y[q]);  if ((y[q] & 1) == 1) {  countEven = countEven + countOdd;  countOdd = 0;  }  }  else {  // Adding to even number  totalSum  = totalSum + (countEven * 1L * y[q]);  if ((y[q] & 1) == 1) {  countOdd = countOdd + countEven;  countEven = 0;  }  }  }  // Returning the final answer  return totalSum;  }  // Driver code  public static void main(String[] args)  {  // Input 1  int n1 = 3, k1 = 3;  int[] arr1 = { 1, 2, 4 };  boolean[] check1 = { false, true, false };  int[] y1 = { 2, 3, 5 };  // Function call  System.out.println(sum(n1, k1, arr1, check1, y1));  // Input 2  int n2 = 6, k2 = 7;  int[] arr2 = { 1, 3, 2, 4, 10, 48 };  boolean[] check2 = { true, false, false, false,  true, false, false };  int[] y2 = { 6, 5, 4, 5, 3, 12, 1 };  // Function call  System.out.println(sum(n2, k2, arr2, check2, y2));  } } 

# Python implementation for the above approach def sum(n, k, arr, check, y): # It will store the final answer total_sum = 0 count_odd, count_even = 0, 0 # Loop for finding the totalSum # and count odd and even for i in range(n): total_sum += arr[i] if arr[i]%2 != 0: count_odd += 1 else: count_even += 1 # Loop for k queries for q in range(k): if check[q]: # Adding to odd number total_sum += count_odd*y[q] if y[q]%2 != 0: count_even += count_odd count_odd = 0 else: # Adding to even number total_sum += count_even*y[q] if y[q]%2 != 0: count_odd += count_even count_even = 0 # Returning the final answer return total_sum # Input 1 n1, k1 = 3, 3 arr1 = [1, 2, 4] check1 = [False, True, False] y1 = [2, 3, 5] # function call print(sum(n1, k1, arr1, check1, y1)) # Input 2 n2, k2 = 6, 7 arr2 = [1, 3, 2, 4, 10, 48] check2 = [True, False, False, False, True, False, False] y2 = [6, 5, 4, 5, 3, 12, 1] # function call print(sum(n2, k2, arr2, check2, y2)) 

using System; using System.Collections.Generic; class Program  {    // Function to calculate the final sum  static long sum(int n, int k, List<int> arr,  List<bool> check, List<int> y)  {    // It will store the final answer  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) != 0)  countOdd++;  else  countEven++;  }  // Loop for k queries  for (int q = 0; q < k; q++) {  if (check[q]) {  // Adding to odd number  totalSum  = totalSum + (countOdd * (long)y[q]);  if ((y[q] & 1) != 0) {  countEven = countEven + countOdd;  countOdd = 0;  }  }  else {  // Adding to even number  totalSum  = totalSum + (countEven * (long)y[q]);  if ((y[q] & 1) != 0) {  countOdd = countOdd + countEven;  countEven = 0;  }  }  }  // Returning the final answer  return totalSum;  }  // Driver code  static void Main(string[] args)  {  // Input 1  int n1 = 3, k1 = 3;  List<int> arr1 = new List<int>{ 1, 2, 4 };  List<bool> check1  = new List<bool>{ false, true, false };  List<int> y1 = new List<int>{ 2, 3, 5 };  // Function call  Console.WriteLine(sum(n1, k1, arr1, check1, y1));  // Input 2  int n2 = 6, k2 = 7;  List<int> arr2  = new List<int>{ 1, 3, 2, 4, 10, 48 };  List<bool> check2  = new List<bool>{ true, false, false, false,  true, false, false };  List<int> y2  = new List<int>{ 6, 5, 4, 5, 3, 12, 1 };  // Function call  Console.WriteLine(sum(n2, k2, arr2, check2, y2));  } } // This code is contributed by divya_p123. 

// JavaScript implementation of the above approach // Function to calculate the final sum function sum(n, k, arr, check, y) {  // It will store the final answer  var totalSum = 0;  var countOdd = 0, countEven = 0;  // Loop for finding the totalSum   // and count odd and even  for (var i = 0; i < n; i++) {  totalSum = totalSum + arr[i];  if (arr[i] & 1) {  countOdd++;  }  else {  countEven++;  }  }  // Loop for k queries  for (var q = 0; q < k; q++) {  if (check[q]) {  // Adding to odd number  totalSum = totalSum + countOdd * y[q];  if (y[q] & 1) {  countEven = countEven + countOdd;  countOdd = 0;  }  }  else {  // Adding to even number  totalSum = totalSum + countEven * y[q];  if (y[q] & 1) {  countOdd = countOdd + countEven;  countEven = 0;  }  }  }  // Returning the final answer  return totalSum; } // Driver code // Input 1 var n1 = 3, k1 = 3; var arr1 = [1, 2, 4]; var check1 = [false, true, false]; var y1 = [2, 3, 5]; // Function call console.log(sum(n1, k1, arr1, check1, y1)); // Input 2 var n2 = 6, k2 = 7; var arr2 = [1, 3, 2, 4, 10, 48]; var check2 = [true, false, false, false, true, false, false]; var y2 = [6, 5, 4, 5, 3, 12, 1]; // Function call console.log(sum(n2, k2, arr2, check2, y2)); // This code is contributed by Prasad Kandekar(prasad264) 

29 196

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