Reorganizar la array dada de manera que cada elemento elevado a su índice sea impar

Posted on by Rudeus Greyrat

Dada una array arr de longitud N , la tarea es reorganizar los elementos de la array dada de modo que para cada elemento, su XOR bit a bit con su índice sea un valor impar. Si no es posible reorganizar, devuelva -1 .

Ejemplo:

Entrada: arr[] = {1 2 4 3 5}
Salida: 1 2 3 4 5
Explicación : en la array anterior:
para el primer elemento: el valor es 1 y el índice es 0 -> entonces 1 ^ 0 = 1, que es impar
para el segundo elemento: el valor es 2 y el índice es 1 -> entonces 2 ^ 1 = 3, lo cual es impar
para el tercer elemento: el valor es 4 y el índice es 2 -> entonces 4 ^ 2 = 6, que es par -> la reorganización será ocurrirá
para el 4.º elemento: el valor es 3 y el índice es 3 -> entonces 3 ^ 3 = 0, que es par -> la reorganización ocurrirá
para el 5.º elemento: el valor es 5 y el índice es 4 -> entonces 5 ^ 4 = 3, que es impar

Entonces, si intercambiamos las posiciones de 4 y 3 como {1, 2, 3, 4, 5}, 
el XOR de 3^2 se convertirá en 1 y el XOR de 4^3 se convertirá en 7, ambos impares. 

Por lo tanto, {1, 2, 3, 4, 5} es uno de los posibles reordenamientos.

Entrada: arr[] = {1 2 7 3 5}
Salida : -1

 

Enfoque: La idea para resolver este problema se basa en las propiedades del operador XOR bit a bit, que:

  • XOR de dos elementos impares siempre es par,
  • XOR de dos elementos pares es siempre par, y
  • XOR de un elemento par e impar siempre es impar.

Entonces, para reorganizar la array según sea necesario, almacenaremos todos los elementos pares en índices impares y los elementos impares en índices pares.

Siga los pasos a continuación para entender cómo: 

  • Primero cuente cuántas arrays de índices pares e impares tienen, que serán siempre n/2 y nn/2 respectivamente
  • Luego cuente cuántos elementos pares e impares tiene la array
  • Almacene los elementos pares e impares de la array por separado
  • Compruebe si el reordenamiento es posible o no, es decir, el recuento de elementos pares es igual a los índices impares y viceversa o no.
  • Si no es posible, devuelve -1.
  • Si la reorganización es posible, inserte todos los elementos impares en los índices pares y los elementos pares en los índices impares.
  • Devuelve la array reorganizada al final.

A continuación se muestra la implementación del enfoque:

C++

// C++ program to Rearrange the array
// Such that A[i]^ i is odd
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange given array
vector<int> rearrange(int arr[], int n)
{
    vector<int> ans;
    int i;
 
    // Count how many odd
    // and even index array have
    int oddIndex = n / 2,
  evenIndex = n - oddIndex;
 
    // Count how many odd
    // and even elements array have
    int oddElement = 0, evenElement = 0;
 
    // Store the even and odd elements
    // of the array separately
    vector<int> odd, even;
 
    for (i = 0; i < n; i++)
        if (arr[i] % 2) {
            oddElement++;
            odd.push_back(arr[i]);
        }
        else {
            evenElement++;
            even.push_back(arr[i]);
        }
 
    // To make XOR of each element
    // with its index as odd,
    // we have to place each even element
    // at an odd index and vice versa
 
    // Therefore check if rearrangement
    // is possible or not
    if (oddElement != evenIndex
        || oddIndex != evenElement) {
        ans.push_back(-1);
    }
 
    // If the rearrangement is possible
    else {
 
        // Insert odd elements at even indices
        // and even elements at odd indices
        int j = 0, k = 0;
        for (int i = 0; i < n; i++)
            if (i % 2)
                ans.push_back(even[j++]);
            else
                ans.push_back(odd[k++]);
    }
 
    // return the rearranged array
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    vector<int> res = rearrange(arr, n);
 
    for (auto i : res)
        cout << i << " ";
    return 0;
}

Java

// Java program to Rearrange the array
// Such that A[i]^ i is odd
import java.io.*;
import java.util.ArrayList; 
 
class GFG {
 
  // Function to rearrange given array
  static void  rearrange(int arr[], int n)
  {
    ArrayList<Integer> ans = new ArrayList<>(); 
 
    // Count how many odd
    // and even index array have
    int oddIndex = n / 2, evenIndex = n - oddIndex;
 
    // Count how many odd
    // and even elements array have
    int oddElement = 0, evenElement = 0;
 
    // Store the even and odd elements
    // of the array separately
    ArrayList<Integer> odd = new ArrayList<>(); 
    ArrayList<Integer> even = new ArrayList<>(); 
 
    for (int i = 0; i < n; i++)
      if (arr[i] % 2 == 1) {
        oddElement++;
        odd.add(arr[i]);
      }
    else {
      evenElement++;
      even.add(arr[i]);
    }
 
    // To make XOR of each element
    // with its index as odd,
    // we have to place each even element
    // at an odd index and vice versa
 
    // Therefore check if rearrangement
    // is possible or not
    if (oddElement != evenIndex
        || oddIndex != evenElement) {
      ans.add(-1);
    }
 
    // If the rearrangement is possible
    else {
 
      // Insert odd elements at even indices
      // and even elements at odd indices
      int j = 0, k = 0;
      for (int i = 0; i < n; i++)
        if (i % 2 == 1)
          ans.add(even.get(j++));
      else
        ans.add(odd.get(k++));
    }
 
    // print the rearranged array
    for(int i = 0; i < ans.size(); i++){
      System.out.print(ans.get(i) + " ");
    }
  }
 
  // Driver Code
  public static void main (String[] args) {
    int[] arr = { 1, 2, 4, 3, 5 };
    int n = arr.length;
 
    rearrange(arr, n);
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# python3 program to Rearrange the array
# Such that A[i]^ i is odd
 
# Function to rearrange given array
def rearrange(arr, n):
 
    ans = []
    i = 0
 
    # Count how many odd
    # and even index array have
    oddIndex = n // 2
    evenIndex = n - oddIndex
 
    # Count how many odd
    # and even elements array have
    oddElement, evenElement = 0, 0
 
    # Store the even and odd elements
    # of the array separately
    odd, even = [], []
 
    for i in range(0, n):
        if (arr[i] % 2):
            oddElement += 1
            odd.append(arr[i])
 
        else:
            evenElement += 1
            even.append(arr[i])
 
        # To make XOR of each element
        # with its index as odd,
        # we have to place each even element
        # at an odd index and vice versa
 
        # Therefore check if rearrangement
        # is possible or not
    if (oddElement != evenIndex
            or oddIndex != evenElement):
        ans.append(-1)
 
        # If the rearrangement is possible
    else:
 
                # Insert odd elements at even indices
                # and even elements at odd indices
        j, k = 0, 0
        for i in range(0, n):
            if (i % 2):
                ans.append(even[j])
                j += 1
 
            else:
                ans.append(odd[k])
                k += 1
 
        # return the rearranged array
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 4, 3, 5]
    n = len(arr)
 
    res = rearrange(arr, n)
 
    for i in res:
        print(i, end=" ")
 
    # This code is contributed by rakeshsahni

C#

// C# program to Rearrange the array
// Such that A[i]^ i is odd
using System;
using System.Collections;
 
class GFG {
 
  // Function to rearrange given array
  static ArrayList rearrange(int[] arr, int n)
  {
    ArrayList ans = new ArrayList();
 
    // Count how many odd
    // and even index array have
    int oddIndex = n / 2, evenIndex = n - oddIndex;
 
    // Count how many odd
    // and even elements array have
    int oddElement = 0, evenElement = 0;
 
    // Store the even and odd elements
    // of the array separately
    ArrayList odd = new ArrayList();
    ArrayList even = new ArrayList();
 
    for (int i = 0; i < n; i++)
      if (arr[i] % 2 == 1) {
        oddElement++;
        odd.Add(arr[i]);
      }
    else {
      evenElement++;
      even.Add(arr[i]);
    }
 
    // To make XOR of each element
    // with its index as odd,
    // we have to place each even element
    // at an odd index and vice versa
 
    // Therefore check if rearrangement
    // is possible or not
    if (oddElement != evenIndex
        || oddIndex != evenElement) {
      ans.Add(-1);
    }
 
    // If the rearrangement is possible
    else {
 
      // Insert odd elements at even indices
      // and even elements at odd indices
      int j = 0, k = 0;
      for (int i = 0; i < n; i++)
        if (i % 2 == 1)
          ans.Add(even[j++]);
      else
        ans.Add(odd[k++]);
    }
 
    // return the rearranged array
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 1, 2, 4, 3, 5 };
    int n = arr.Length;
 
    ArrayList res = rearrange(arr, n);
 
    for (int i = 0; i < res.Count; i++) {
      Console.Write(res[i] + " ");
    }
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to rearrange given array
       function rearrange(arr, n) {
           let ans = [];
           let i;
 
           // Count how many odd
           // and even index array have
           let oddIndex = Math.floor(n / 2),
               evenIndex = n - oddIndex;
 
           // Count how many odd
           // and even elements array have
           let oddElement = 0, evenElement = 0;
 
           // Store the even and odd elements
           // of the array separately
           let odd = [], even = [];
 
           for (i = 0; i < n; i++)
               if (arr[i] % 2) {
                   oddElement++;
                   odd.push(arr[i]);
               }
               else {
                   evenElement++;
                   even.push(arr[i]);
               }
 
           // To make XOR of each element
           // with its index as odd,
           // we have to place each even element
           // at an odd index and vice versa
 
           // Therefore check if rearrangement
           // is possible or not
           if (oddElement != evenIndex
               || oddIndex != evenElement) {
               ans.push_back(-1);
           }
 
           // If the rearrangement is possible
           else {
 
               // Insert odd elements at even indices
               // and even elements at odd indices
               let j = 0, k = 0;
               for (let i = 0; i < n; i++)
                   if (i % 2)
                       ans.push(even[j++]);
                   else
                       ans.push(odd[k++]);
           }
 
           // return the rearranged array
           return ans;
       }
 
       // Driver Code
       let arr = [1, 2, 4, 3, 5];
       let n = arr.length;
 
       let res = rearrange(arr, n);
 
       for (let i of res)
           document.write(i + " ")
 
      // This code is contributed by Potta Lokesh
   </script>
Producción

1 2 3 4 5

Complejidad temporal: O(N).
Espacio Auxiliar: O(N).

Publicación traducida automáticamente

Artículo escrito por nobita04 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *