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.