Dada una array arr[] que tiene N enteros positivos, la tarea es encontrar todos los índices i (1 ≤ i ≤ N – 1) tales que, la suma del conteo de números pares en el subarreglo izquierdo [0, i – 1 ] y el recuento de números impares en el subarreglo derecho [i, n – 1] es el máximo entre todos los i.
Ejemplo:
Entrada: arr[] = {1, 3, 4, 5, 6}
Salida: 1 3
Explicación: el recuento de enteros pares en el rango de 0 a 0 es 0 y el recuento de enteros impares en el rango de 1 a 4 es 2.
Total = 0 + 2 = 2 (que es máximo para todas las i).
El conteo de enteros pares en el rango de 0 a 2 es 1 y el conteo de enteros impares en el rango de 3 a 4 es 1.
Total = 1 + 1 = 2 (que es el máximo para todas las i).Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida: 2 4 6
Explicación: el conteo de enteros pares en el rango de 0 a 1 es 1 y el conteo de enteros impares en el rango de 2 a 6 es 3.
Total = 1 + 3 = 4 (que es el máximo para todas las i). El recuento de enteros pares en el rango de 0 a 3 es 2 y el recuento de enteros impares en el rango de 4 a 6 es 2. Total = 2 + 2 = 4 (que es el máximo para todas las i). El recuento de enteros pares en el rango de 0 a 5 es 3 y el recuento de enteros impares en el rango de 6 a 6 es 1. Total = 3 + 1 = 4 (que es el máximo para todas las i).
Enfoque ingenuo: para cada índice, verifique el número de enteros pares a la izquierda y el número de enteros impares a la derecha. Encuentre el valor máximo entre estos y los índices que dan como resultado el valor máximo. Siga los pasos que se mencionan a continuación:
- Para cada índice i :
- Iterar en el subarreglo izquierdo [0, i – 1] usando un bucle anidado y contar el número de enteros pares en el subarreglo izquierdo.
- De manera similar, en otro ciclo anidado, itere en el subarreglo derecho [i, N – 1] y cuente el número de enteros impares en este subarreglo.
- Use una variable entera que mantendrá el registro de la suma máxima de conteos.
- Compare la suma con la suma máxima anterior
- Si la suma actual es mayor que la anterior, actualice la suma máxima y coloque i en la array de resultados.
- si la suma actual es igual al máximo anterior, entonces en la array de resultados anterior empuje este índice i.
- Devuelve el vector resultante.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the answer vector vector<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 answer void print(vector<int>& ans) { int n = ans.size(); for (int i = 0; i < n; i++) cout << ans[i] << ' '; } // Driver code int 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 approach import 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 vector def 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 answer def pnt(ans): n = len(ans) for i in range(0, n): print(ans[i], end=' ') # Driver code if __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 approach using 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>
2 4 6
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(1)
Enfoque eficiente: podemos usar la técnica de la suma de prefijos para compensar el tiempo. El enfoque se analiza a continuación:
- Para realizar un seguimiento del recuento de elementos pares de 0 a i – 1 para cualquier i , declare una array de countEven . Inicializarlo con ceros inicialmente.
- Además, para realizar un seguimiento del recuento de elementos impares de i an – 1 para cualquier i , declare una array de countOdd . Inicializarlo con ceros inicialmente.
- Entonces, para cada i, la suma será countEven[i-1]+countOdd[i-1]
- Compara la suma con la suma máxima anterior
- Si la suma actual es mayor que la anterior, actualice la suma máxima y coloque i en la array de resultados.
- si la suma actual es igual al máximo anterior, entonces en la array de resultados anterior empuje este índice i.
- Devuelve el vector resultante después de completar el recorrido.
A continuación se muestra la implementación del enfoque anterior.
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 elements void 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 code int 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 approach import 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
2 4 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)