Dada una array de N enteros. Necesitamos encontrar un índice tal que la frecuencia de los números pares en su lado izquierdo sea igual a la frecuencia de los números pares en su lado derecho o la frecuencia de los números impares en su lado izquierdo sea igual a la frecuencia de los números impares en su lado derecho. Si no existe tal índice en una array, imprima -1 De lo contrario, imprima el índice requerido. Nota: (si existe más de un índice, devuelva el índice que viene primero)
Ejemplos:
Input : arr[] = {4, 3, 2, 1, 2, 4}
Output : index = 2
Explanation: At index 2, there is one
odd number on its left and one odd on
its right.
Input :arr[] = { 1, 2, 4, 5, 8, 3, 12}
Output : index = 3
Método 1: (Enfoque simple)
Ejecute dos bucles. Para cada elemento, cuente pares e impares en sus lados izquierdo y derecho.
C++
// CPP program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
#include <iostream>
using namespace std;
// Function to find index
int findIndex(int arr[], int n) {
for (int i = 0; i < n; i++) {
int odd_left = 0, even_left = 0;
int odd_right = 0, even_right = 0;
// To count Even and Odd numbers of left side
for (int j = 0; j < i; j++) {
if (arr[j] % 2 == 0)
even_left++;
else
odd_left++;
}
// To count Even and Odd numbers of right side
for (int k = n - 1; k > i; k--) {
if (arr[k] % 2 == 0)
even_right++;
else
odd_right++;
}
// To check Even Or Odd of Both sides are equal or not
if (even_right == even_left || odd_right == odd_left)
return i;
}
return -1;
}
// Driver's Function
int main() {
int arr[] = {4, 3, 2, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int index = findIndex(arr, n);
((index == -1) ? cout << "-1" :
cout << "index = " << index);
return 0;
}
Java
// Java program to find
// an index which has
// same number of even
// elements on left and
// right, Or same number
// of odd elements on
// left and right.
class GFG{
// Function to find index
static int findIndex(int arr[], int n) {
for (int i = 0; i < n; i++) {
int odd_left = 0, even_left = 0;
int odd_right = 0, even_right = 0;
// To count Even and Odd
// numbers of left side
for (int j = 0; j < i; j++) {
if (arr[j] % 2 == 0)
even_left++;
else
odd_left++;
}
// To count Even and Odd
// numbers of right side
for (int k = n - 1; k > i; k--) {
if (arr[k] % 2 == 0)
even_right++;
else
odd_right++;
}
// To check Even Or Odd of Both
// sides are equal or not
if (even_right == even_left || odd_right == odd_left)
return i;
}
return -1;
}
// Driver's Function
public static void main(String[] args) {
int arr[] = {4, 3, 2, 1, 2};
int n = arr.length;
int index = findIndex(arr, n);
if (index == -1)
System.out.println("-1");
else{
System.out.print("index = ");
System.out.print(index);
}
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
'''Python program to find
an index which has
same number of even
elements on left and
right, Or same number
of odd elements on
left and right.'''
# Function to find index
def findIndex(arr,n):
for i in range(n):
odd_left = 0
even_left = 0
odd_right = 0
even_right = 0
# To count Even and Odd
# numbers of left side
for j in range(i):
if (arr[j] % 2 == 0):
even_left=even_left+1
else:
odd_left=odd_left+1
# To count Even and Odd
# numbers of right side
for k in range(n - 1, i, -1):
if (arr[k] % 2 == 0):
even_right=even_right+1
else:
odd_right=odd_right+1
# To check Even Or Odd of Both
# sides are equal or not
if (even_right == even_left and odd_right == odd_left):
return i
return -1
# Driver's Function
arr = [4, 3, 2, 1, 2]
n = len(arr)
index = findIndex(arr, n)
if (index == -1):
print("-1")
else:
print("index = ", index)
# This code is contributed
# by Anant Agarwal.
C#
// C# program to find an index which has
// same number of even elements on left
// and right, Or same number of odd
// elements on left and right.
using System;
class GFG{
// Function to find index
static int findIndex(int []arr, int n) {
for (int i = 0; i < n; i++) {
int odd_left = 0, even_left = 0;
int odd_right = 0, even_right = 0;
// To count Even and Odd
// numbers of left side
for (int j = 0; j < i; j++) {
if (arr[j] % 2 == 0)
even_left++;
else
odd_left++;
}
// To count Even and Odd
// numbers of right side
for (int k = n - 1; k > i; k--) {
if (arr[k] % 2 == 0)
even_right++;
else
odd_right++;
}
// To check Even Or Odd of Both
// sides are equal or not
if (even_right == even_left ||
odd_right == odd_left)
return i;
}
return -1;
}
// Driver's Function
public static void Main() {
int []arr = {4, 3, 2, 1, 2};
int n = arr.Length;
int index = findIndex(arr, n);
if (index == -1)
Console.Write("-1");
else{
Console.Write("index = ");
Console.Write(index);
}
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
// Function to find index
function findIndex($arr, $n)
{
for ($i = 0; $i < $n; $i++)
{
$odd_left = 0;
$even_left = 0;
$odd_right = 0;
$even_right = 0;
// To count Even and Odd
// numbers of left side
for ($j = 0; $j < $i; $j++)
{
if ($arr[$j] % 2 == 0)
$even_left++;
else
$odd_left++;
}
// To count Even and Odd
// numbers of right side
for ($k = $n - 1; $k > $i; $k--)
{
if ($arr[$k] % 2 == 0)
$even_right++;
else
$odd_right++;
}
// To check Even Or Odd of
// Both sides are equal or not
if ($even_right == $even_left ||
$odd_right == $odd_left)
return $i;
}
return -1;
}
// Drivers Code
{
$arr = array(4, 3, 2, 1, 2);
$n = sizeof($arr) / sizeof($arr[0]);
$index = findIndex($arr, $n);
if($index == -1)
echo "-1";
else
echo ("index = $index" );
return 0;
}
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
// Function to find index
function findIndex(arr, n) {
for (let i = 0; i < n; i++) {
let odd_left = 0, even_left = 0;
let odd_right = 0, even_right = 0;
// To count Even and Odd numbers of left side
for (let j = 0; j < i; j++) {
if (arr[j] % 2 == 0)
even_left++;
else
odd_left++;
}
// To count Even and Odd numbers of right side
for (let k = n - 1; k > i; k--) {
if (arr[k] % 2 == 0)
even_right++;
else
odd_right++;
}
// To check Even Or Odd of Both sides are equal or not
if (even_right == even_left || odd_right == odd_left)
return i;
}
return -1;
}
// Driver's Function
let arr = [4, 3, 2, 1, 2];
let n = arr.length;
let index = findIndex(arr, n);
if (index == -1)
document.write("-1");
else{
document.write("index = ");
document.write(index);
}
//This code is contributed by Mayank Tyagi
</script>
Producción:
index = 2
Complejidad temporal: O(n*n)
Espacio auxiliar: O(1)
Método 2: (Solución eficiente)
1- Cree dos vectores de tipos de pares, es decir, v_left y v_right
2- v_left[i] almacena la frecuencia de los números pares e impares de sus lados izquierdos
3- v_right[i] almacena la frecuencia de los pares e impares números de sus lados derechos
4- Ahora comprueba (v_izquierda[i].primero == v_derecha[i].primero || v_izquierda[i].segundo == v_derecha[i].segundo)
si es Verdadero devuelve i
5- Por último si no existe tal índice devuelve -1
C++
// CPP program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to Find index
int Find_Index(int n, int arr[]) {
int odd = 0, even = 0;
// Create two vectors of pair type
vector<pair<int, int>> v_left, v_right;
v_left.push_back(make_pair(odd, even));
for (int i = 0; i < n - 1; i++) {
if (arr[i] % 2 == 0)
even++;
else
odd++;
v_left.push_back(make_pair(odd, even));
}
odd = 0, even = 0;
v_right.push_back(make_pair(odd, even));
for (int i = n - 1; i > 0; i--) {
if (arr[i] % 2 == 0)
even++;
else
odd++;
v_right.push_back(make_pair(odd, even));
}
reverse(v_right.begin(), v_right.end());
for (int i = 0; i < v_left.size(); i++) {
// To check even or odd of Both sides are
// equal or not
if (v_left[i].first == v_right[i].first ||
v_left[i].second == v_right[i].second)
return i;
}
return -1;
}
// Driver's Function
int main() {
int arr[] = {4, 3, 2, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int index = Find_Index(n, arr);
((index == -1) ? cout << "-1" : cout << "index = " << index);
return 0;
}
Java
// Java program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
import java.util.*;
class GFG
{
public static class pair
{
int first, second;
pair(int f, int s)
{
first = f;
second = s;
}
};
// Function to Find index
static int Find_Index(int n, int arr[])
{
int odd = 0, even = 0;
// Create two vectors of pair type
Vector<pair> v_left = new Vector<>();;
Vector<pair> v_right = new Vector<>();
v_left.add(new pair(odd, even));
for (int i = 0; i < n - 1; i++)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_left.add(new pair(odd, even));
}
odd = 0;
even = 0;
v_right.add(new pair(odd, even));
for (int i = n - 1; i > 0; i--)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_right.add(new pair(odd, even));
}
Collections.reverse(v_right);
for (int i = 0; i < v_left.size(); i++)
{
// To check even or odd of Both sides are
// equal or not
if (v_left.get(i).first == v_right.get(i).first
|| v_left.get(i).second == v_right.get(i).second)
{
return i;
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {4, 3, 2, 1, 2};
int n = arr.length;
int index = Find_Index(n, arr);
if (index == -1)
{
System.out.println("-1");
}
else
{
System.out.println("index = " + index);
}
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python program to find an index which has
# same number of even elements on left and
# right, Or same number of odd elements on
# left and right.
class pair:
def __init__(self, f, s):
self.first = f
self.second = s
# Function to Find index
def Find_Index(n, arr):
odd, even = 0, 0
# Create two vectors of pair type
v_left = []
v_right = []
v_left.append(pair(odd, even))
for i in range(n-1):
if (arr[i] % 2 == 0):
even += 1
else:
odd += 1
v_left.append(pair(odd, even))
odd = 0
even = 0
v_right.append(pair(odd, even))
for i in range(n-1,0,-1):
if (arr[i] % 2 == 0):
even += 1
else:
odd += 1
v_right.append(pair(odd, even))
v_right = v_right[::-1]
for i in range(len(v_left)):
# To check even or odd of Both sides are
# equal or not
if (v_left[i].first == v_right[i].first or v_left[i].second == v_right[i].second):
return i
return -1
# Driver code
arr = [4, 3, 2, 1, 2]
n = len(arr)
index = Find_Index(n, arr)
if (index == -1):
print("-1")
else:
print("index = " + str(index))
# This code is contributed by shinjanpatra
C#
// C# program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
using System;
using System.Collections.Generic;
class GFG
{
public class pair
{
public int first, second;
public pair(int f, int s)
{
first = f;
second = s;
}
};
// Function to Find index
static int Find_Index(int n, int []arr)
{
int odd = 0, even = 0;
// Create two vectors of pair type
List<pair> v_left = new List<pair>();;
List<pair> v_right = new List<pair>();
v_left.Add(new pair(odd, even));
for (int i = 0; i < n - 1; i++)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_left.Add(new pair(odd, even));
}
odd = 0;
even = 0;
v_right.Add(new pair(odd, even));
for (int i = n - 1; i > 0; i--)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_right.Add(new pair(odd, even));
}
v_right.Reverse();
for (int i = 0; i < v_left.Count; i++)
{
// To check even or odd of Both sides are
// equal or not
if (v_left[i].first == v_right[i].first ||
v_left[i].second == v_right[i].second)
{
return i;
}
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {4, 3, 2, 1, 2};
int n = arr.Length;
int index = Find_Index(n, arr);
if (index == -1)
{
Console.WriteLine("-1");
}
else
{
Console.WriteLine("index = " + index);
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find an index which has
// same number of even elements on left and
// right, Or same number of odd elements on
// left and right.
class pair
{
constructor(f,s)
{
this.first = f;
this.second = s;
}
}
// Function to Find index
function Find_Index(n,arr)
{
let odd = 0, even = 0;
// Create two vectors of pair type
let v_left = [];
let v_right = [];
v_left.push(new pair(odd, even));
for (let i = 0; i < n - 1; i++)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_left.push(new pair(odd, even));
}
odd = 0;
even = 0;
v_right.push(new pair(odd, even));
for (let i = n - 1; i > 0; i--)
{
if (arr[i] % 2 == 0)
{
even++;
}
else
{
odd++;
}
v_right.push(new pair(odd, even));
}
v_right.reverse();
for (let i = 0; i < v_left.length; i++)
{
// To check even or odd of Both sides are
// equal or not
if (v_left[i].first == v_right[i].first
|| v_left[i].second == v_right[i].second)
{
return i;
}
}
return -1;
}
// Driver code
let arr = [4, 3, 2, 1, 2];
let n = arr.length;
let index = Find_Index(n, arr);
if (index == -1)
{
document.write("-1");
}
else
{
document.write("index = " + index);
}
// This code is contributed by rag2127
</script>
Producción:
index = 2
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Optimización adicional: Podemos optimizar el espacio utilizado en el programa. En lugar de hacer vectores de pares, podemos hacer vectores de números enteros. Podemos usar el hecho de que el número de elementos impares es igual al total de elementos menos el número total de elementos pares. De manera similar, el número de elementos pares es igual al total de elementos menos el número total de elementos impares.