Dada una array arr[] , la tarea es reorganizar los elementos de la array intercambiando elementos adyacentes de modo que ningún elemento permanezca en la misma posición después del intercambio.
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 4, 5 }
Salida: 2 1 5 3 4
Explicación:
Los elementos adyacentes se intercambian de la siguiente manera:
(1, 2 -> 2, 1)
(3, 4, 5 – > 5, 3, 4)
Entrada: arr[] = {1, 2, 3, 4}
Salida: 2 1 4 3
Explicación:
Los elementos adyacentes se intercambian de la siguiente manera:
1, 2 -> 2, 1
3, 4 -> 4, 3
Enfoque: La observación clave en el problema es que puede haber dos casos para que las arrays intercambien los elementos de la array:
- Si la longitud de la array es par, podemos intercambiar fácilmente 2 variables sin usar la tercera variable para cada par de elementos contiguos.
- Si la longitud de la array es impar, entonces podemos hacer lo mismo que arriba, pero los últimos 3 elementos no formarán un par, por lo que podemos intercambiar fácilmente esas 3 variables sin usar la cuarta variable .
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
void print(int a[], int n)
{
// Loop to iterate over the
// elements of array
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
// Function to swap two variables without
// using the third variable
void swapTwo(int& x, int& y)
{
// Store XOR of all in x
x = x ^ y;
// After this, y has value of x
y = x ^ y;
// After this, x has value of y
x = x ^ y;
}
// Function to swap three variables
// without using fourth variable
void swapThree(int& a, int& b, int& c)
{
// Store XOR of all in a
a = a ^ b ^ c;
// After this, b has value of a
b = a ^ b ^ c;
// After this, c has value of b
c = a ^ b ^ c;
// After this, a has value of c
a = a ^ b ^ c;
}
// Function that swaps n integers
void rearrangeArray(int a[], int n)
{
if (n % 2 == 0) {
for (int i = 0; i < n - 1; i += 2) {
// Swap 2 variables without
// using 3rd variable
swapTwo(a[i], a[i + 1]);
}
}
else {
for (int i = 0; i < n - 3; i += 2) {
// Swap 2 variables without
// using 3rd variable
swapTwo(a[i], a[i + 1]);
}
// The last 3 elements will not form
// pair if n is odd
// Hence, swapp 3 variables without
// using 4th variable
swapThree(a[n - 1], a[n - 2], a[n - 3]);
}
// Print the array elements
print(a, n);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
rearrangeArray(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to print the array
static void print(int a[], int n)
{
// Loop to iterate over the
// elements of array
for(int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
// Function to swap two variables without
// using the third variable
static void swapTwo(int x, int y, int[] a)
{
// Store XOR of all in x
a[x] = a[x] ^ a[y];
// After this, y has value of x
a[y] = a[x] ^ a[y];
// After this, x has value of y
a[x] = a[x] ^ a[y];
}
// Function to swap three variables
// without using fourth variable
static void swapThree(int x, int y,
int z, int[] a)
{
// Store XOR of all in a
a[x] = a[x] ^ a[y] ^ a[z];
// After this, b has value of a
a[y] = a[x] ^ a[y] ^ a[z];
// After this, c has value of b
a[z] = a[x] ^ a[y] ^ a[z];
// After this, a has value of c
a[x] = a[x] ^ a[y] ^ a[z];
}
// Function that swaps n integers
static void rearrangeArray(int a[], int n)
{
if (n % 2 == 0)
{
for(int i = 0; i < n - 1; i += 2)
{
// Swap 2 variables without
// using 3rd variable
swapTwo(i, i + 1, a);
}
}
else
{
for(int i = 0; i < n - 3; i += 2)
{
// Swap 2 variables without
// using 3rd variable
swapTwo(i, i + 1, a);
}
// The last 3 elements will not form
// pair if n is odd
// Hence, swapp 3 variables without
// using 4th variable
swapThree(n - 1, n - 2, n - 3, a);
}
// Print the array elements
print(a, n);
}
// Driver code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
// Function call
rearrangeArray(arr, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to print the array def print1(a, n): # Loop to iterate over the # elements of array for i in range(n): print(a[i], end = " ") # Function to swap two variables without # using the third variable def swapTwo(x, y): # Store XOR of all in x x = x ^ y # After this, y has value of x y = x ^ y # After this, x has value of y x = x ^ y return x, y # Function to swap three variables # without using fourth variable def swapThree(a, b, c): # Store XOR of all in a a = a ^ b ^ c # After this, b has value of a b = a ^ b ^ c # After this, c has value of b c = a ^ b ^ c # After this, a has value of c a = a ^ b ^ c return a , b , c # Function that swaps n integers def rearrangeArray(a, n): if (n % 2 == 0): for i in range (0, n - 1, 2): # Swap 2 variables without # using 3rd variable a[i], a[i + 1] = swapTwo(a[i], a[i + 1]) else: for i in range(0, n - 3, 2): # Swap 2 variables without # using 3rd variable a[i], a[i + 1] = swapTwo(a[i], a[i + 1]) # The last 3 elements will not form # pair if n is odd # Hence, swapp 3 variables without # using 4th variable a[n - 1], a[n - 2], a[n - 3] = swapThree(a[n - 1], a[n - 2], a[n - 3]) # Print the array elements print1(a, n) # Driver Code if __name__ == "__main__": # Given array arr[] arr = [1, 2, 3, 4, 5 ] n = len(arr) # Function call rearrangeArray(arr, n) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to print the array
static void print(int []a, int n)
{
// Loop to iterate over the
// elements of array
for(int i = 0; i < n; i++)
Console.Write(a[i] + " ");
}
// Function to swap two variables without
// using the third variable
static void swapTwo(ref int x, ref int y)
{
// Store XOR of all in x
x = x ^ y;
// After this, y has value of x
y = x ^ y;
// After this, x has value of y
x = x ^ y;
}
// Function to swap three variables
// without using fourth variable
static void swapThree(ref int a, ref int b,
ref int c)
{
// Store XOR of all in a
a = a ^ b ^ c;
// After this, b has value of a
b = a ^ b ^ c;
// After this, c has value of b
c = a ^ b ^ c;
// After this, a has value of c
a = a ^ b ^ c;
}
// Function that swaps n integers
static void rearrangeArray(int []a, int n)
{
if (n % 2 == 0)
{
for(int i = 0; i < n - 1; i += 2)
{
// Swap 2 variables without
// using 3rd variable
swapTwo(ref a[i], ref a[i + 1]);
}
}
else
{
for(int i = 0; i < n - 3; i += 2)
{
// Swap 2 variables without
// using 3rd variable
swapTwo(ref a[i], ref a[i + 1]);
}
// The last 3 elements will not form
// pair if n is odd
// Hence, swapp 3 variables without
// using 4th variable
swapThree(ref a[n - 1], ref a[n - 2],
ref a[n - 3]);
}
// Print the array elements
print(a, n);
}
// Driver Code
public static void Main(string []s)
{
// Given array arr[]
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
// Function call
rearrangeArray(arr, n);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for the above approach
// Function to print the array
function print( a, n)
{
// Loop to iterate over the
// elements of array
for (var i = 0; i < n; i++)
document.write( a[i] + " ");
}
// Function that swaps n integers
function rearrangeArray( a, n)
{
if (n % 2 == 0) {
for (var i = 0; i < n - 1; i += 2) {
// Swap 2 variables without
// using 3rd variable
// Store XOR of all in x
a[i] = a[i] ^ a[i + 1];
// After this, y has value of x
a[i + 1] = a[i] ^ a[i + 1];
// After this, x has value of y
a[i] = a[i] ^ a[i + 1];
}
}
else {
for (var i = 0; i < n - 3; i += 2) {
// Swap 2 variables without
// using 3rd variable
// Store XOR of all in x
a[i] = a[i] ^ a[i + 1];
// After this, y has value of x
a[i + 1] = a[i] ^ a[i + 1];
// After this, x has value of y
a[i] = a[i] ^ a[i + 1];
}
// The last 3 elements will not form
// pair if n is odd
// Hence, swapp 3 variables without
// using 4th variable
// Store XOR of all in a
a[n-1] = a[n-1] ^ a[n - 2] ^ a[n - 3];
// After this, b has value of a
a[n - 2] = a[n-1] ^ a[n - 2] ^ a[n - 3];
// After this, c has value of b
a[n - 3] = a[n-1] ^ a[n - 2] ^ a[n - 3];
// After this, a has value of c
a[n-1] = a[n-1] ^ a[n - 2] ^ a[n - 3];
}
// Print the array elements
print(a, n);
}
// Driver Code
// Given array arr[]
var arr = [ 1, 2, 3, 4, 5 ];
var n = arr.length;
// Function Call
rearrangeArray(arr, n);
</script>
Producción:
2 1 4 5 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)