Dada una array circular arr[] de tamaño N , la tarea es encontrar los siguientes enteros de la misma paridad para cada elemento en arr[] . Si los siguientes enteros con la misma paridad no existen, devuelve -1 para ese número.
Ejemplos :
Entrada : arr[] = {2, 4, 3, 6, 5}
Salida : 4 6 5 2 3
Explicación: Para 2, el siguiente elemento con la misma paridad es 4.
Para 4, el siguiente elemento con la misma paridad es 6.
Para 3, el siguiente elemento con la misma paridad es 5.
Para 6, el siguiente elemento con la misma paridad es 2.
Para 5, el siguiente elemento con la misma paridad es 3.Entrada : arr[] = {5, 4, 7, 6}
Salida : 7 6 5 4
Planteamiento : La idea para resolver el problema es la siguiente:
Iterar desde la parte posterior de la array. Si el arr[i] es impar, entonces actuará como el siguiente elemento impar para cualquier entero impar situado en j donde j < i y j es el más cercano a i . Lo mismo es cierto para los elementos pares también.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables para almacenar el siguiente impar ( Next_Odd ) y el siguiente par ( Next_Even ) para el elemento de array actual.
- Iterar de i = 2*n-1 a 0:
- Si i ≥ n , entonces el ciclo se usa para encontrar el siguiente par e impar para el último elemento par e impar de la array.
- De lo contrario, si arr[i] es impar y hay otro elemento impar presente, coloque Next_Odd en la array resultante y actualice Next_Odd para que sea arr[i] .
- Si arr[i] es par y hay otro elemento par presente, coloque Next_Even en la array resultante y actualice Next_Even para que sea arr[i] .
- Devuelve la array resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return next same parity
// element in the array
vector<int> findElement(int* arr, int n)
{
// Initialize the vector with -1
vector<int> SPE(n, -1);
int Next_Even, Next_Odd;
// To check if odd and even
// are more than one or not
int Count_Even = 0, Count_Odd = 0;
for (int i = 2 * n - 1; i >= 0; i--) {
// Duplicate array
if (i >= n) {
if (arr[i % n] & 1) {
Next_Odd = arr[i % n];
Count_Odd++;
}
else {
Next_Even = arr[i % n];
Count_Even++;
}
}
// Original array
else {
if (arr[i] & 1) {
if (Count_Odd > 1) {
SPE[i] = Next_Odd;
Next_Odd = arr[i];
}
}
else {
if (Count_Even > 1) {
SPE[i] = Next_Even;
Next_Even = arr[i];
}
}
}
}
return SPE;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 3, 6, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
vector<int> v = findElement(arr, N);
for (auto i : v) {
cout << i << " ";
}
}
Java
// Java code to implement the above approach
import java.util.*;
public class GFG {
// Function to return next same parity
// element in the array
static int[] findElement(int[] arr, int n)
{
// Initialize the vector with -1
int[] SPE = new int[n];
for (int i = 0; i < n; i++) {
SPE[i] = -1;
}
int Next_Even = 0, Next_Odd = 0;
// To check if odd and even
// are more than one or not
int Count_Even = 0, Count_Odd = 0;
for (int i = 2 * n - 1; i >= 0; i--) {
// Duplicate array
if (i >= n) {
if ((arr[i % n] & 1) == 1) {
Next_Odd = arr[i % n];
Count_Odd++;
}
else {
Next_Even = arr[i % n];
Count_Even++;
}
}
// Original array
else {
if ((arr[i] & 1) == 1) {
if (Count_Odd > 1) {
SPE[i] = Next_Odd;
Next_Odd = arr[i];
}
}
else {
if (Count_Even > 1) {
SPE[i] = Next_Even;
Next_Even = arr[i];
}
}
}
}
return SPE;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 2, 4, 3, 6, 5 };
int N = arr.length;
// Function call
int[] v = findElement(arr, N);
for (int i = 0; i < v.length; i++) {
System.out.print(v[i] + " ");
}
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to return next same parity
function findElement(arr, n) {
// Initialize the vector with -1
let SPE = new Array(n).fill(-1);
let Next_Even, Next_Odd;
// To check if odd and even
// are more than one or not
let Count_Even = 0, Count_Odd = 0;
for (let i = 2 * n - 1; i >= 0; i--) {
// Duplicate array
if (i >= n) {
if (arr[i % n] & 1) {
Next_Odd = arr[i % n];
Count_Odd++;
}
else {
Next_Even = arr[i % n];
Count_Even++;
}
}
// Original array
else {
if (arr[i] & 1) {
if (Count_Odd > 1) {
SPE[i] = Next_Odd;
Next_Odd = arr[i];
}
}
else {
if (Count_Even > 1) {
SPE[i] = Next_Even;
Next_Even = arr[i];
}
}
}
}
return SPE;
}
// Driver Code
let arr = [2, 4, 3, 6, 5];
let N = arr.length;
// Function call
let v = findElement(arr, N);
for (let i of v) {
document.write(i + " ");
}
// This code is contributed by Potta Lokesh
</script>
Python3
# Python program for the above approach # Function to return next same parity def findElement(arr, n): # Initialize the vector with -1 SPE = [-1] * n Next_Even = None Next_Odd = None # To check if odd and even # are more than one or not Count_Even = 0 Count_Odd = 0 for i in range(2 * n - 1, -1, -1): # Duplicate array if (i >= n): if (arr[i % n] & 1): Next_Odd = arr[i % n] Count_Odd += 1 else: Next_Even = arr[i % n] Count_Even += 1 # Original array else: if (arr[i] & 1): if (Count_Odd > 1): SPE[i] = Next_Odd Next_Odd = arr[i] else: if (Count_Even > 1): SPE[i] = Next_Even Next_Even = arr[i] return SPE # Driver Code arr = [2, 4, 3, 6, 5] N = len(arr) # Function call v = findElement(arr, N) for i in v: print(i, end=" ") # This code is contributed by Saurabh Jaiswal
C#
using System;
public class GFG{
static public void Main (){
// Code
}
4 6 5 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA