Given an array arr[] having N positive integers, the task is to find all the indices i (1 ≤ i ≤ N – 1) such that, the sum of the count of even numbers in the left subarray [0, i – 1] and the count of odd numbers in the right subarray [i, n – 1] is the maximum among all i’s.
Example:
Input: arr[] = {1, 3, 4, 5, 6}
Output: 1 3
Explanation: Count of even integers in the range 0 to 0 is 0 and count of odd integers in the range 1 to 4 is 2.
Total = 0 + 2 = 2 (which is maximum for all i’s).
Count of even integers in the range 0 to 2 is 1 and count of odd integers in the range 3 to 4 is 1.
Total = 1 + 1 = 2 (which is maximum for all i’s).Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 2 4 6
Explanation: Count of even integers in the range 0 to 1 is 1 and count of odd integer in the range 2 to 6 is 3.
Total = 1 + 3 = 4 (which is maximum for all i’s).
Count of even integers in the range 0 to 3 is 2 and Count of odd integers in the range 4 to 6 is 2.
Total = 2 + 2 = 4 (which is maximum for all i’s).
Count of even integers in the range 0 to 5 is 3 and Count of odd integers in the range 6 to 6 is 1.
Total = 3 + 1 = 4 (which is maximum for all i’s).
Naive Approach: For each index check number of even integers to the left and the number of odd integers to the right. Find the maximum value among these and the indices which result in the maximum value. Follow the steps mentioned below:
- For each index i:
- Iterate in the left subarray [0, i – 1] using a nested loop and count the number of even integers in the left subarray.
- Similarly, in another nested loop, iterate in the right subarray [i, N – 1] and count the number of odd integers in this subarray.
- Use an integer variable that will keep the track of the maximum sum of counts.
- Compare the sum with the previous max sum
- If the current sum is greater than the previous one then update the max sum and put i in the result array.
- if the current sum is equal to the previous maximum one then in the previous result array push this index i.
- Return the resultant vector.
Below is the implementation of the above approach
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the answer vectorvector<int> solve(vector<int>& vect){ // To keep the track // of final answer int maximumSum = 0; // Size of nums int n = vect.size(); // It keeps the track // of final answer vector<int> ans; // Iterate over the indices for (int i = 1; i < n; i++) { // Stores the count of even // numbers in the left subarray int countEven = 0; // Iterate in the left subarray for (int j = i - 1; j >= 0; j--) { if (vect[j] % 2 == 0) countEven++; } // Stores the count of even // numbers in the left subarray int countOdd = 0; // Iterate in the right subarray for (int j = i; j < n; j++) { if (vect[j] % 2 == 1) countOdd++; } // Stores the sum for current i int sum = countEven + countOdd; // If current score // is greater than // previous then push // in the ans array. if (sum > maximumSum) { ans = { i }; maximumSum = sum; } // If sum is equal to // maximum sum then // consider the index i // with previous max else if (sum == maximumSum) ans.push_back(i); } return ans;}// Function to print answervoid print(vector<int>& ans){ int n = ans.size(); for (int i = 0; i < n; i++) cout << ans[i] << ' ';}// Driver codeint main(){ // Given vector vector<int> vect = { 1, 2, 3, 4, 5, 6, 7 }; // Function call vector<int> ans = solve(vect); print(ans); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the answer arraylist public static ArrayList<Integer> solve(int vect[]) { // To keep the track // of final answer int maximumSum = 0; // Size of nums int n = vect.length; // It keeps the track // of final answer ArrayList<Integer> ans = new ArrayList<Integer>(); // Iterate over the indices for (int i = 1; i < n; i++) { // Stores the count of even // numbers in the left subarray int countEven = 0; // Iterate in the left subarray for (int j = i - 1; j >= 0; j--) { if (vect[j] % 2 == 0) countEven++; } // Stores the count of even // numbers in the left subarray int countOdd = 0; // Iterate in the right subarray for (int j = i; j < n; j++) { if (vect[j] % 2 == 1) countOdd++; } // Stores the sum for current i int sum = countEven + countOdd; // If current score // is greater than // previous then push // in the ans array. if (sum > maximumSum) { ans.clear(); ans.add(i); maximumSum = sum; } // If sum is equal to // maximum sum then // consider the index i // with previous max else if (sum == maximumSum) ans.add(i); } return ans; } // Function to print answer public static void print(ArrayList<Integer> ans) { int n = ans.size(); for (int i = 0; i < n; i++) System.out.print(ans.get(i) + " "); } public static void main(String[] args) { int vect[] = { 1, 2, 3, 4, 5, 6, 7 }; // Function call ArrayList<Integer> ans = solve(vect); print(ans); }}// This code is contributed by Rohit Pradhan |
Python3
# python3 code to implement the approach# Function to find the answer vectordef solve(vect): # To keep the track # of final answer maximumSum = 0 # Size of nums n = len(vect) # It keeps the track # of final answer ans = [] # Iterate over the indices for i in range(1, n): # Stores the count of even # numbers in the left subarray countEven = 0 # Iterate in the left subarray for j in range(i-1, -1, -1): if (vect[j] % 2 == 0): countEven += 1 # Stores the count of even # numbers in the left subarray countOdd = 0 # Iterate in the right subarray for j in range(i, n): if (vect[j] % 2 == 1): countOdd += 1 # Stores the sum for current i sum = countEven + countOdd # If current score # is greater than # previous then push # in the ans array. if (sum > maximumSum): ans = [i] maximumSum = sum # If sum is equal to # maximum sum then # consider the index i # with previous max elif (sum == maximumSum): ans.append(i) return ans# Function to print answerdef pnt(ans): n = len(ans) for i in range(0, n): print(ans[i], end=' ')# Driver codeif __name__ == "__main__": # Given vector vect = [1, 2, 3, 4, 5, 6, 7] # Function call ans = solve(vect) pnt(ans) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approachusing System;using System.Collections;class GFG { // Function to find the answer vector static ArrayList solve(ArrayList vect) { // To keep the track // of final answer int maximumSum = 0; // Size of nums int n = vect.Count; // It keeps the track // of final answer ArrayList ans = new ArrayList(); // Iterate over the indices for (int i = 1; i < n; i++) { // Stores the count of even // numbers in the left subarray int countEven = 0; // Iterate in the left subarray for (int j = i - 1; j >= 0; j--) { if ((int)vect[j] % 2 == 0) countEven++; } // Stores the count of even // numbers in the left subarray int countOdd = 0; // Iterate in the right subarray for (int j = i; j < n; j++) { if ((int)vect[j] % 2 == 1) countOdd++; } // Stores the sum for current i int sum = countEven + countOdd; // If current score // is greater than // previous then push // in the ans array. if (sum > maximumSum) { ans.Clear(); ans.Add(i); maximumSum = sum; } // If sum is equal to // maximum sum then // consider the index i // with previous max else if (sum == maximumSum) ans.Add(i); } return ans; } // Function to print answer static void print(ArrayList ans) { int n = ans.Count; for (int i = 0; i < n; i++) Console.Write(ans[i] + " "); } // Driver code public static void Main() { // Given vector ArrayList vect = new ArrayList(); vect.Add(1); vect.Add(2); vect.Add(3); vect.Add(4); vect.Add(5); vect.Add(6); vect.Add(7); // Function call ArrayList ans = solve(vect); print(ans); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the answer vector function solve(vect) { // To keep the track // of final answer let maximumSum = 0; // Size of nums let n = vect.length; // It keeps the track // of final answer let ans = []; // Iterate over the indices for (let i = 1; i < n; i++) { // Stores the count of even // numbers in the left subarray let countEven = 0; // Iterate in the left subarray for (let j = i - 1; j >= 0; j--) { if (vect[j] % 2 == 0) countEven++; } // Stores the count of even // numbers in the left subarray let countOdd = 0; // Iterate in the right subarray for (let j = i; j < n; j++) { if (vect[j] % 2 == 1) countOdd++; } // Stores the sum for current i let sum = countEven + countOdd; // If current score // is greater than // previous then push // in the ans array. if (sum > maximumSum) { ans = [i]; maximumSum = sum; } // If sum is equal to // maximum sum then // consider the index i // with previous max else if (sum == maximumSum) ans.push(i); } return ans; } // Function to print answer function print(ans) { let n = ans.length; for (let i = 0; i < n; i++) document.write(ans[i] + ' ') } // Driver code // Given vector let vect = [1, 2, 3, 4, 5, 6, 7]; // Function call let ans = solve(vect); print(ans); // This code is contributed by Potta Lokesh </script> |
Output
2 4 6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: We can use the prefix sum technique to trade off the time. The approach is discussed below:
- To keep the track of the count of even elements from 0 to i – 1 for any i, declare an array of countEven. Initialize it with zeroes initially.
- Also, to keep the track of the count of odd elements from i to n – 1 for any i, declare an array of countOdd. Initialize it with zeroes initially.
- Then for each i the sum will be countEven[i-1]+countOdd[i-1]
- Compare the sum with previous max sum
- If current sum is greater than the previous one then update the max sum and put i in the result array .
- if current sum is equal to the previous max one then in previous result array push this index i.
- Return the resultant vector after complete traversal.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;vector<int> solve(vector<int>& vect){ // The size of the vector int n = vect.size(); // It keeps the track of the maximumSum int maximumSum = 0; // Initialize vectors vector<int> countEven(n, 0); vector<int> countOdd(n, 0); // Traverse and update countEven vector for (int i = 0; i < n; i++) { if (i == 0) { if (vect[i] % 2 == 0) countEven[i] = 1; else countEven[i] = 0; } else { if (vect[i] % 2 == 0) countEven[i] = countEven[i - 1] + 1; else countEven[i] = countEven[i - 1]; } } // Traverse and update countOdd vector for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { if (vect[i] % 2 == 1) countOdd[i] = 1; else countOdd[i] = 0; } else { if (vect[i] % 2 == 1) countOdd[i] = countOdd[i + 1] + 1; else countOdd[i] = countOdd[i + 1]; } } // ans will store the indices vector<int> ans; for (int i = 1; i < n; i++) { // Calculate current sum int sum = countEven[i - 1] + countOdd[i]; maximumSum = max(maximumSum, sum); } // Iterate over the indices for (int i = 1; i < n; i++) { int sum = countEven[i - 1] + countOdd[i]; // If the value of sum is // equal to maximumSum then // consider the index i if (sum == maximumSum) ans.push_back(i); } // Return the ans vector return ans;}// Function to print ans elementsvoid print(vector<int>& ans){ // Number of elements in the answer vector int n = ans.size(); // Print values for (int i = 0; i < n; i++) cout << ans[i] << ' ';}// Driver codeint main(){ // Input vector vector<int> nums = { 1, 2, 3, 4, 5, 6, 7 }; // Calling solve function vector<int> ans = solve(nums); // Print ans elements print(ans); return 0;} |
Java
// JAVA code to implement the approachimport java.util.*;class GFG { public static ArrayList<Integer> solve(ArrayList<Integer> vect) { // The size of the vector int n = vect.size(); // It keeps the track of the maximumSum int maximumSum = 0; // Initialize vectors int[] countEven = new int[n]; for (int i = 0; i < n; i++) { countEven[i] = 0; } int[] countOdd = new int[n]; for (int i = 0; i < n; i++) { countOdd[i] = 0; } // Traverse and update countEven vector for (int i = 0; i < n; i++) { if (i == 0) { if (vect.get(i) % 2 == 0) countEven[i] = 1; else countEven[i] = 0; } else { if (vect.get(i) % 2 == 0) countEven[i] = countEven[i - 1] + 1; else countEven[i] = countEven[i - 1]; } } // Traverse and update countOdd vector for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { if (vect.get(i) % 2 == 1) countOdd[i] = 1; else countOdd[i] = 0; } else { if (vect.get(i) % 2 == 1) countOdd[i] = countOdd[i + 1] + 1; else countOdd[i] = countOdd[i + 1]; } } // ans will store the indices ArrayList<Integer> ans = new ArrayList<>(); for (int i = 1; i < n; i++) { // Calculate current sum int sum = countEven[i - 1] + countOdd[i]; maximumSum = Math.max(maximumSum, sum); } // Iterate over the indices for (int i = 1; i < n; i++) { int sum = countEven[i - 1] + countOdd[i]; // If the value of sum is // equal to maximumSum then // consider the index i if (sum == maximumSum) ans.add(i); } // Return the ans vector return ans; } // Function to print ans elements public static void print(ArrayList<Integer> ans) { // Number of elements in the answer vector int n = ans.size(); // Print values for (int i = 0; i < n; i++) System.out.print(ans.get(i) + " "); } // Driver code public static void main(String[] args) { // Input vector ArrayList<Integer> nums = new ArrayList<Integer>( Arrays.asList(1, 2, 3, 4, 5, 6, 7)); // Calling solve function ArrayList<Integer> ans = solve(nums); // Print ans elements print(ans); }}// This code is contributed by Taranpreet |
Python3
# C++ code to implement the approachdef solve(vect): # The size of the vector n = len(vect) # It keeps the track of the maximumSum maximumSum = 0 # Initialize vectors countEven = [0]*n countOdd = [0]*n # Traverse and update countEven vector for i in range(n): if (i == 0): if (vect[i] % 2 == 0): countEven[i] = 1 else: countEven[i] = 0 else: if (vect[i] % 2 == 0): countEven[i] = countEven[i - 1] + 1 else: countEven[i] = countEven[i - 1] # Traverse and update countOdd vector for i in range(n-1, -1, -1): if (i == n - 1): if (vect[i] % 2 == 1): countOdd[i] = 1 else: countOdd[i] = 0 else: if (vect[i] % 2 == 1): countOdd[i] = countOdd[i + 1] + 1 else: countOdd[i] = countOdd[i + 1] # ans will store the indices ans = [] for i in range(1, n): # Calculate current sum sum = countEven[i - 1] + countOdd[i] maximumSum = max(maximumSum, sum) # Iterate over the indices for i in range(1, n): sum = countEven[i - 1] + countOdd[i] # If the value of sum is # equal to maximumSum then # consider the index i if (sum == maximumSum): ans.append(i) # Return the ans vector return ans# Function to print ans elementsdef printAns(ans): # Number of elements in the answer vector n = len(ans) # Print values for i in range(n): print(ans[i], end=' ')# Driver code # Input vectornums = [1, 2, 3, 4, 5, 6, 7]# Calling solve functionans = solve(nums)printAns(ans)# This code is contributed by vikkycirus. |
C#
using System;using System.Collections.Generic;class GFG{ public static List<int> solve(List<int> vect) { // The size of the vector int n = vect.Count; // It keeps the track of the maximumSum int maximumSum = 0; // Initialize vectors int[] countEven = new int[n]; for (int i = 0; i < n; i++) { countEven[i] = 0; } int[] countOdd = new int[n]; for (int i = 0; i < n; i++) { countOdd[i] = 0; } // Traverse and update countEven vector for (int i = 0; i < n; i++) { if (i == 0) { if (vect[i] % 2 == 0) countEven[i] = 1; else countEven[i] = 0; } else { if (vect[i] % 2 == 0) countEven[i] = countEven[i - 1] + 1; else countEven[i] = countEven[i - 1]; } } // Traverse and update countOdd vector for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { if (vect[i] % 2 == 1) countOdd[i] = 1; else countOdd[i] = 0; } else { if (vect[i] % 2 == 1) countOdd[i] = countOdd[i + 1] + 1; else countOdd[i] = countOdd[i + 1]; } } // ans will store the indices List<int> ans = new List<int>(); for (int i = 1; i < n; i++) { // Calculate current sum int sum = countEven[i - 1] + countOdd[i]; maximumSum = Math.Max(maximumSum, sum); } // Iterate over the indices for (int i = 1; i < n; i++) { int sum = countEven[i - 1] + countOdd[i]; // If the value of sum is // equal to maximumSum then // consider the index i if (sum == maximumSum) ans.Add(i); } // Return the ans vector return ans; } // Function to print ans elements public static void print(List<int> ans) { // Number of elements in the answer vector int n = ans.Count; // Print values for (int i = 0; i < n; i++) Console.Write(ans[i] + " ");}public static void Main(string[] args){// Input listList<int> nums = new List<int> { 1, 2, 3, 4, 5, 6, 7 }; // Calling Solve function List<int> ans = solve(nums); // Print ans elements print(ans);}} |
Javascript
function solve(vect) { // The size of the vector const n = vect.length; // It keeps the track of the maximumSum let maximumSum = 0; // Initialize arrays const countEven = new Array(n).fill(0); const countOdd = new Array(n).fill(0); // Traverse and update countEven array for (let i = 0; i < n; i++) { if (i == 0) { if (vect[i] % 2 == 0) countEven[i] = 1; else countEven[i] = 0; } else { if (vect[i] % 2 == 0) countEven[i] = countEven[i - 1] + 1; else countEven[i] = countEven[i - 1]; } } // Traverse and update countOdd array for (let i = n - 1; i >= 0; i--) { if (i == n - 1) { if (vect[i] % 2 == 1) countOdd[i] = 1; else countOdd[i] = 0; } else { if (vect[i] % 2 == 1) countOdd[i] = countOdd[i + 1] + 1; else countOdd[i] = countOdd[i + 1]; } } // ans will store the indices const ans = []; for (let i = 1; i < n; i++) { // Calculate current sum const sum = countEven[i - 1] + countOdd[i]; maximumSum = Math.max(maximumSum, sum); } // Iterate over the indices for (let i = 1; i < n; i++) { const sum = countEven[i - 1] + countOdd[i]; // If the value of sum is // equal to maximumSum then // consider the index i if (sum == maximumSum) ans.push(i); } // Return the ans array return ans;}// Function to print ans elementsfunction print(ans) { // Number of elements in the answer array const n = ans.length; // Print values for (let i = 0; i < n; i++) console.log(ans[i] + ' ');}// Driver codeconst nums = [1, 2, 3, 4, 5, 6, 7];// Calling solve functionconst ans = solve(nums);// Print ans elementsprint(ans); |
Output
2 4 6
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
