Dada una array arr[] de tamaño N (N > 3) , la tarea es encontrar la posición del elemento que difiere en paridad (par/impar) con respecto a todos los demás elementos de la array.
Nota: Se garantiza que siempre habrá un número que difiera en paridad de todos los demás elementos.
Ejemplos:
Entrada: arr[] = {2, 4, 7, 8, 10}
Salida: 2
Explicación: El único elemento impar en la array es 7 (= arr[2]). Por lo tanto, la salida requerida es 2.Entrada: arr[] = {2, 1, 1}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver este problema es almacenar todos los números pares e impares con sus índices en un mapa múltiple e imprimir el índice del elemento presente en el mapa con tamaño 1 . Siga los pasos a continuación para resolver el problema:
- Inicialice dos Multimap , para números pares e impares.
- Recorra la array y almacene los elementos de la array en sus respectivos mapas múltiples junto con sus índices.
- Ahora encuentre el Multimap con un tamaño igual a 1 . Imprime el índice del elemento de array almacenado en ese Multimap .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
// element which differs in parity
// with the remaining array elements
int OddOneOut(int arr[], int N)
{
// Multimaps to store even
// and odd numbers along
// with their indices
multimap<int, int> e, o;
// Traverse the array
for (int i = 0; i < N; i++) {
// If array element is even
if (arr[i] % 2 == 0) {
e.insert({ arr[i], i });
}
// Otherwise
else {
o.insert({ arr[i], i });
}
}
// If only one even element
// is present in the array
if (e.size() == 1) {
cout << e.begin()->second;
}
// If only one odd element
// is present in the array
else {
cout << o.begin()->second;
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 4, 7, 8, 10 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
OddOneOut(arr, N);
return 0;
}
Python3
# Python3 program for the above approach
# Function to print the array
# element which differs in parity
# with the remaining array elements
def OddOneOut(arr, N) :
# Multimaps to store even
# and odd numbers along
# with their indices
e, o = {}, {}
# Traverse the array
for i in range(N) :
# If array element is even
if (arr[i] % 2 == 0) :
e[arr[i]] = i
# Otherwise
else :
o[arr[i]] = i
# If only one even element
# is present in the array
if (len(e) == 1) :
print(list(e.values())[0] )
# If only one odd element
# is present in the array
else :
print(list(o.values())[0] )
# Given array
arr = [ 2, 4, 7, 8, 10 ]
# Size of the array
N = len(arr)
OddOneOut(arr, N)
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function to print the array
// element which differs in parity
// with the remaining array elements
static void OddOneOut(int[] arr, int N)
{
// Multimaps to store even
// and odd numbers along
// with their indices
Dictionary<int, int> e = new Dictionary<int, int>();
Dictionary<int, int> o = new Dictionary<int, int>();
// Traverse the array
for (int i = 0; i < N; i++) {
// If array element is even
if (arr[i] % 2 == 0) {
e[arr[i]] = i;
}
// Otherwise
else {
o[arr[i]] = i;
}
}
// If only one even element
// is present in the array
if (e.Count == 1) {
Console.Write(e.First().Value);
}
// If only one odd element
// is present in the array
else {
Console.Write(o.First().Value);
}
}
// Driver Code
public static void Main(string[] args)
{
// Given array
int[] arr = { 2, 4, 7, 8, 10 };
// Size of the array
int N = arr.Length;
OddOneOut(arr, N);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// Javascript program for the above approach
// Function to print the array
// element which differs in parity
// with the remaining array elements
function OddOneOut(arr,N)
{
// Multimaps to store even
// and odd numbers along
// with their indices
let e = new Map();
let o = new Map();
// Traverse the array
for (let i = 0; i < N; i++) {
// If array element is even
if (arr[i] % 2 == 0) {
e.set(arr[i] , i);
}
// Otherwise
else {
o.set(arr[i] , i);
}
}
// If only one even element
// is present in the array
if (e.size == 1) {
document.write(Array.from(e.values())[0]) ;
}
// If only one odd element
// is present in the array
else {
document.write(Array.from(o.values())[0]) ;
}
}
// Driver Code
// Given array
let arr=[2, 4, 7, 8, 10];
// Size of the array
let N = arr.length;
OddOneOut(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es mantener un conteo de elementos de array pares e impares en dos variables y verificar qué conteo es igual a 1 . Siga los pasos a continuación para resolver el problema:
- Mantenga cuatro variables even, odd , para contar los elementos de array pares e impares en la array, y lastOdd, lastEven para almacenar los índices de los últimos elementos de array pares e impares encontrados.
- Después de atravesar la array , si se encuentra que impar es 1 , entonces imprima lastOdd .
- De lo contrario, imprima lastEven .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the element
// which differs in parity
int oddOneOut(int arr[], int N)
{
// Stores the count of odd and
// even array elements encountered
int odd = 0, even = 0;
// Stores the indices of the last
// odd and even array elements encountered
int lastOdd = 0, lastEven = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If array element is even
if (arr[i] % 2 == 0) {
even++;
lastEven = i;
}
// Otherwise
else {
odd++;
lastOdd = i;
}
}
// If only one odd element
// is present in the array
if (odd == 1) {
cout << lastOdd << endl;
}
// If only one even element
// is present in the array
else {
cout << lastEven << endl;
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 4, 7, 8, 10 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
oddOneOut(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to print the element
// which differs in parity
static void oddOneOut(int arr[], int N)
{
// Stores the count of odd and
// even array elements encountered
int odd = 0, even = 0;
// Stores the indices of the last
// odd and even array elements encountered
int lastOdd = 0, lastEven = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If array element is even
if (arr[i] % 2 == 0) {
even++;
lastEven = i;
}
// Otherwise
else {
odd++;
lastOdd = i;
}
}
// If only one odd element
// is present in the array
if (odd == 1) {
System.out.println(lastOdd);
}
// If only one even element
// is present in the array
else {
System.out.println(lastEven);
}
}
// Driver Code
public static void main(String args[])
{
// Given array
int arr[] = { 2, 4, 7, 8, 10 };
// Size of the array
int N = arr.length;
oddOneOut(arr, N);
}
}
// This code is contributed by jana_sayantan.
Python3
# Python program for the above approach # Function to print the element # which differs in parity def oddOneOut(arr, N) : # Stores the count of odd and # even array elements encountered odd = 0 even = 0 # Stores the indices of the last # odd and even array elements encountered lastOdd = 0 lastEven = 0 # Traverse the array for i in range(N): # If array element is even if (arr[i] % 2 == 0) : even += 1 lastEven = i # Otherwise else : odd += 1 lastOdd = i # If only one odd element # is present in the array if (odd == 1) : print(lastOdd) # If only one even element # is present in the array else : print(lastEven) # Driver Code # Given array arr = [ 2, 4, 7, 8, 10 ] # Size of the array N = len(arr) oddOneOut(arr, N) # This code is contributed by susmitakundugoaldanga.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to print the element
// which differs in parity
static void oddOneOut(int[] arr, int N)
{
// Stores the count of odd and
// even array elements encountered
int odd = 0, even = 0;
// Stores the indices of the last
// odd and even array elements encountered
int lastOdd = 0, lastEven = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If array element is even
if (arr[i] % 2 == 0)
{
even++;
lastEven = i;
}
// Otherwise
else
{
odd++;
lastOdd = i;
}
}
// If only one odd element
// is present in the array
if (odd == 1)
{
Console.WriteLine(lastOdd);
}
// If only one even element
// is present in the array
else
{
Console.WriteLine(lastEven);
}
}
// Driver code
static void Main()
{
// Given array
int[] arr = { 2, 4, 7, 8, 10 };
// Size of the array
int N = arr.Length;
oddOneOut(arr, N);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
// Function to print the element
// which differs in parity
function oddOneOut(arr, N)
{
// Stores the count of odd and
// even array elements encountered
let odd = 0, even = 0;
// Stores the indices of the last
// odd and even array elements encountered
let lastOdd = 0, lastEven = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
// If array element is even
if (arr[i] % 2 == 0)
{
even++;
lastEven = i;
}
// Otherwise
else
{
odd++;
lastOdd = i;
}
}
// If only one odd element
// is present in the array
if (odd == 1)
{
document.write(lastOdd);
}
// If only one even element
// is present in the array
else
{
document.write(lastEven);
}
}
// Driver code
// Given array
let arr = [ 2, 4, 7, 8, 10 ];
// Size of the array
let N = arr.length;
oddOneOut(arr, N);
// This code is contributed by suresh07
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)