Dada una array arr[] de elementos únicos y tres enteros X , A y B . La tarea es imprimir la máxima distancia posible entre los elementos A y B en como máximo X intercambios con los elementos adyacentes.
Ejemplos:
Entrada: arr[] = {5, 1, 3, 2}, X = 1, A = 2, B = 3
Salida: 2
Explicación:
3 se intercambia con su elemento adyacente 1. Entonces, la distancia entre el elemento 3 y 2 es 2 y no son posibles más intercambios ya que X = 1.
Entrada: arr = {100, 33, 10, 1}, X = 5, A = 100, B = 1
Salida: 3
Explicación:
Como los elementos ya son el comienzo y elemento final, la distancia entre ellos ya está maximizada.
Enfoque: Se pueden seguir los siguientes pasos para calcular el resultado:
- En caso de que la X dada sea 0, entonces |índice(A)-índice(B)| se devuelve como respuesta final.
- Si los elementos ya están en el índice 0 y n-1, devuelva N-1 ya que la distancia ya está maximizada.
- De lo contrario, el elemento de índice mayor se intercambia X veces con su elemento adyacente hasta que sea menor que el tamaño de la array.
- Después de llegar al final de la array si X > 0; luego, el elemento de índice más pequeño se intercambia con sus elementos anteriores hasta que X no es igual a 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to maximize the distance
// between the two elements of the
// array by at most X swaps
void max_distance(int a[], int n, int x,
int A, int B)
{
// Initialize the variables
int g = 0, h = 0;
// Iterate till the length of the array
for (int i = 0; i < n; i++) {
// Check if current element is A
if (a[i] == A)
// Store index
g = i;
// Check if current element is B
if (a[i] == B)
// Store index
h = i;
}
// If X = 0, swapping can not be done
if (x == 0) {
cout << abs(g - h);
}
// If elements are at starting and ending
// indices, then the distance
// is already maximum
else if ((g == 0) && (h == (n - 1)))
cout << n - 1 << endl;
else if ((g == n - 1) && (h == 0))
cout << n - 1 << endl;
else {
// Greater index is incremented
// till x > 0 and the
// index of element < size of array
if (h > g) {
while ((x > 0) && (h < n - 1)) {
h++;
x--;
}
// Check if reached the size of array
// and x > 0, then the
// smaller index is decremented
if (x > 0) {
while ((x > 0) && (g > 0)) {
g--;
x--;
}
}
cout << h - g << endl;
}
// Greater index is incremented till x>0
// and index of element < size of array
else {
while ((x > 0) && (g < n - 1)) {
g++;
x--;
}
// Check if reached the size of the array
// and x > 0 the smaller index
// is decremented
if (x > 0) {
while ((x > 0) && (h > 0)) {
h--;
x--;
}
}
cout << g - h << endl;
}
}
}
// Driver code
int main()
{
int a[] = { 100, 33, 10, 1 };
int x = 5, A = 100, B = 1;
int n = sizeof(a) / sizeof(a[0]);
max_distance(a, n, x, A, B);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to maximize the distance
// between the two elements of the
// array by at most X swaps
static void max_distance(int a[], int n, int x,
int A, int B)
{
// Initialize the variables
int i, g = 0, h = 0;
// Iterate till the length of the array
for(i = 0; i < n; i++)
{
// Check if current element is A
if (a[i] == A)
// Store index
g = i;
// Check if current element is B
if (a[i] == B)
// Store index
h = i;
}
// If X = 0, swapping can not be done
if (x == 0)
{
System.out.print(Math.abs(g - h));
}
// If elements are at starting and
// ending indices, then the distance
// is already maximum
else if ((g == 0) && (h == (n - 1)))
System.out.println(n - 1);
else if ((g == n - 1) && (h == 0))
System.out.println(n - 1);
else
{
// Greater index is incremented
// till x > 0 and theindex of
// element < size of array
if (h > g)
{
while ((x > 0) && (h < n - 1))
{
h++;
x--;
}
// Check if reached the size of
// array and x > 0, then the
// smaller index is decremented
if (x > 0)
{
while ((x > 0) && (g > 0))
{
g--;
x--;
}
}
System.out.println(h - g);
}
// Greater index is incremented till x>0
// and index of element < size of array
else
{
while ((x > 0) && (g < n - 1))
{
g++;
x--;
}
// Check if reached the size of the array
// and x > 0 the smaller index
// is decremented
if (x > 0)
{
while ((x > 0) && (h > 0))
{
h--;
x--;
}
}
System.out.println(g - h);
}
}
}
// Driver code
public static void main (String []args)
{
int a[] = { 100, 33, 10, 1 };
int x = 5, A = 100, B = 1;
int n = a.length;
max_distance(a, n, x, A, B);
}
}
// This code is contributed by chitranayal
Python3
# Python3 program for the above approach # Function to maximize the distance # between the two elements of the # array by at most X swaps def max_distance(a, n, x, A, B): # Initialize the variables g = 0 h = 0 for i in range(0, n): # Check if current element is A if (a[i] == A): # Store index g = i # Check if current element is B if (a[i] == B): # Store index h = i # If X = 0, swapping can not be done if (x == 0): print(abs(g - h)) # If elements are at starting and # ending indices, then the distance # is already maximum elif ((g == 0) and (h == (n - 1))): print(n - 1, end = '') elif ((g == n - 1) and (h == 0)): print(n - 1, end = '') else: # Greater index is incremented # till x > 0 and the # index of element < size of array if (h > g): while ((x > 0) and (h < n - 1)): h += 1 x -= 1 # Check if reached the size # of array and x > 0, then the # smaller index is decremented if (x > 0): while ((x > 0) and (g > 0)): g -= 1 x -= 1 print(h - g, end = '') # Greater index is incremented till x>0 # and index of element < size of array else: while ((x > 0) and (g < n - 1)): g += 1 x -= 1 # Check if reached the size of # the array and x > 0 the smaller # index is decremented if (x > 0): while ((x > 0) and (h > 0)): h -= 1 x -= 1 print(g - h, end = '') # Driver code if __name__ == '__main__': a = [ 100, 33, 10, 1 ] x = 5 A = 100 B = 1 n = len(a) max_distance(a, n, x, A, B) # This code is contributed by virusbuddah_
C#
// C# program for the above approach
using System;
class GFG{
// Function to maximize the distance
// between the two elements of the
// array by at most X swaps
static void max_distance(int []a, int n, int x,
int A, int B)
{
// Initialize the variables
int i, g = 0, h = 0;
// Iterate till the length of the array
for(i = 0; i < n; i++)
{
// Check if current element is A
if (a[i] == A)
// Store index
g = i;
// Check if current element is B
if (a[i] == B)
// Store index
h = i;
}
// If X = 0, swapping can not be done
if (x == 0)
{
Console.Write(Math.Abs(g - h));
}
// If elements are at starting and
// ending indices, then the distance
// is already maximum
else if ((g == 0) && (h == (n - 1)))
Console.WriteLine(n - 1);
else if ((g == n - 1) && (h == 0))
Console.WriteLine(n - 1);
else
{
// Greater index is incremented
// till x > 0 and theindex of
// element < size of array
if (h > g)
{
while ((x > 0) && (h < n - 1))
{
h++;
x--;
}
// Check if reached the size of
// array and x > 0, then the
// smaller index is decremented
if (x > 0)
{
while ((x > 0) && (g > 0))
{
g--;
x--;
}
}
Console.WriteLine(h - g);
}
// Greater index is incremented till x>0
// and index of element < size of array
else
{
while ((x > 0) && (g < n - 1))
{
g++;
x--;
}
// Check if reached the size of the
// array and x > 0 the smaller index
// is decremented
if (x > 0)
{
while ((x > 0) && (h > 0))
{
h--;
x--;
}
}
Console.WriteLine(g - h);
}
}
}
// Driver code
public static void Main(String []args)
{
int []a = { 100, 33, 10, 1 };
int x = 5, A = 100, B = 1;
int n = a.Length;
max_distance(a, n, x, A, B);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to maximize the distance
// between the two elements of the
// array by at most X swaps
function max_distance(a,n,x,A,B)
{
// Initialize the variables
let i, g = 0, h = 0;
// Iterate till the length of the array
for(i = 0; i < n; i++)
{
// Check if current element is A
if (a[i] == A)
// Store index
g = i;
// Check if current element is B
if (a[i] == B)
// Store index
h = i;
}
// If X = 0, swapping can not be done
if (x == 0)
{
document.write(Math.abs(g - h));
}
// If elements are at starting and
// ending indices, then the distance
// is already maximum
else if ((g == 0) && (h == (n - 1)))
document.write(n - 1);
else if ((g == n - 1) && (h == 0))
document.write(n - 1);
else
{
// Greater index is incremented
// till x > 0 and theindex of
// element < size of array
if (h > g)
{
while ((x > 0) && (h < n - 1))
{
h++;
x--;
}
// Check if reached the size of
// array and x > 0, then the
// smaller index is decremented
if (x > 0)
{
while ((x > 0) && (g > 0))
{
g--;
x--;
}
}
document.write(h - g);
}
// Greater index is incremented till x>0
// and index of element < size of array
else
{
while ((x > 0) && (g < n - 1))
{
g++;
x--;
}
// Check if reached the size of the array
// and x > 0 the smaller index
// is decremented
if (x > 0)
{
while ((x > 0) && (h > 0))
{
h--;
x--;
}
}
document.write(g - h);
}
}
}
// Driver code
let a=[ 100, 33, 10, 1];
let x = 5, A = 100, B = 1;
let n = a.length;
max_distance(a, n, x, A, B);
// This code is contributed by rag2127
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por Akshita207 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA