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>
Producción
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
Producción
2 4 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)