Dado un anillo circular que tiene marcas de 1 a N. Dados dos números A y B , puede pararse en cualquier lugar (digamos X ) y contar la suma total de la distancia (digamos Z , es decir, la distancia de X a A + la distancia de X a B ). La tarea es elegir X de tal manera que Z se minimice. Imprime el valor de Z así obtenido. Tenga en cuenta que X no puede ser ni igual a A ni ser igual a B .
Ejemplos:
Entrada: N = 6, A = 2, B = 4
Salida: 2
Elija X como 3, de modo que la distancia de X a A sea 1, y la distancia de X a B sea 1.
Entrada: N = 4, A = 1, B = 2
Salida: 3
Elija X como 3 o 4, ambos dan la distancia como 3.
Aproximación: Hay dos caminos entre las posiciones A y B en el círculo, uno en el sentido de las agujas del reloj y otro en el sentido contrario a las agujas del reloj. Un valor óptimo para Z es elegir X como cualquier punto en la ruta mínima entre A y B , entonces Z será igual a la distancia mínima entre las posiciones, excepto en el caso en que ambas posiciones sean adyacentes, es decir, la distancia mínima es 1 . En ese caso, X no se puede elegir como el punto entre ellos ya que debe ser diferente tanto de A como de B y el resultado será 3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum value of Z
int findMinimumZ(int n, int a, int b)
{
// Change elements such that a < b
if (a > b)
swap(a, b);
// Distance from (a to b)
int distClock = b - a;
// Distance from (1 to a) + (b to n)
int distAntiClock = (a - 1) + (n - b + 1);
// Minimum distance between a and b
int minDist = min(distClock, distAntiClock);
// If both the positions are
// adjacent on the circle
if (minDist == 1)
return 3;
// Return the minimum Z possible
return minDist;
}
// Driver code
int main()
{
int n = 4, a = 1, b = 2;
cout << findMinimumZ(n, a, b);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum value of Z
static int findMinimumZ(int n, int a, int b)
{
// Change elements such that a < b
if (a > b)
{
swap(a, b);
}
// Distance from (a to b)
int distClock = b - a;
// Distance from (1 to a) + (b to n)
int distAntiClock = (a - 1) + (n - b + 1);
// Minimum distance between a and b
int minDist = Math.min(distClock, distAntiClock);
// If both the positions are
// adjacent on the circle
if (minDist == 1)
{
return 3;
}
// Return the minimum Z possible
return minDist;
}
private static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
// Driver code
public static void main(String[] args)
{
int n = 4, a = 1, b = 2;
System.out.println(findMinimumZ(n, a, b));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python 3 implementation of the approach # Function to return the minimum value of Z def findMinimumZ(n, a, b): # Change elements such that a < b if (a > b): temp = a a = b b = temp # Distance from (a to b) distClock = b - a # Distance from (1 to a) + (b to n) distAntiClock = (a - 1) + (n - b + 1) # Minimum distance between a and b minDist = min(distClock, distAntiClock) # If both the positions are # adjacent on the circle if (minDist == 1): return 3 # Return the minimum Z possible return minDist # Driver code if __name__ == '__main__': n = 4 a = 1 b = 2 print(findMinimumZ(n, a, b)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum value of Z
static int findMinimumZ(int n, int a, int b)
{
// Change elements such that a < b
if (a > b)
{
swap(a, b);
}
// Distance from (a to b)
int distClock = b - a;
// Distance from (1 to a) + (b to n)
int distAntiClock = (a - 1) + (n - b + 1);
// Minimum distance between a and b
int minDist = Math.Min(distClock, distAntiClock);
// If both the positions are
// adjacent on the circle
if (minDist == 1)
{
return 3;
}
// Return the minimum Z possible
return minDist;
}
private static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
// Driver code
static public void Main ()
{
int n = 4, a = 1, b = 2;
Console.WriteLine(findMinimumZ(n, a, b));
}
}
/* This code contributed by ajit*/
PHP
<?php
//PHP implementation of the approach
// Function to return the minimum value of Z
function findMinimumZ($n, $a, $b)
{
// Change elements such that a < b
if ($a > $b)
$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;
// Distance from (a to b)
$distClock = $b - $a;
// Distance from (1 to a) + (b to n)
$distAntiClock = ($a - 1) + ($n - $b + 1);
// Minimum distance between a and b
$minDist = min($distClock, $distAntiClock);
// If both the positions are
// adjacent on the circle
if ($minDist == 1)
return 3;
// Return the minimum Z possible
return $minDist;
}
// Driver code
$n = 4;
$a = 1;
$b = 2;
echo findMinimumZ($n, $a, $b);
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum value of Z
function findMinimumZ(n,a,b)
{
// Change elements such that a < b
if (a > b)
{
swap(a, b);
}
// Distance from (a to b)
let distClock = b - a;
// Distance from (1 to a) + (b to n)
let distAntiClock = (a - 1) + (n - b + 1);
// Minimum distance between a and b
let minDist = Math.min(distClock, distAntiClock);
// If both the positions are
// adjacent on the circle
if (minDist == 1)
{
return 3;
}
// Return the minimum Z possible
return minDist;
}
function swap(x,y)
{
let temp = x;
x = y;
y = temp;
}
// Driver code
let n = 4, a = 1, b = 2;
document.write(findMinimumZ(n, a, b));
// This code is contributed by sravan kumar Gottumukkala
</script>
3
Complejidad de tiempo: O(1), ya que solo hay una operación aritmética básica que toma tiempo constante.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.