Dada una array arr[] . La tarea es encontrar el valor de X tal que el resultado de la expresión (A[1] – X)^2 + (A[2] – X)^2 + (A[3] – X)^2 + … (A[n-1] – X)^2 + (A[n] – X)^2 es el mínimo posible.
Ejemplos:
Entrada: arr[] = {6, 9, 1, 6, 1, 3, 7}
Salida: 5
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 3
Enfoque:
Podemos simplificar la expresión que necesitamos minimizar. La expresión se puede escribir como
(A[1]^2 + A[2]^2 + A[3]^2 + … + A[n]^2) + nX^2 – 2X(A[1] + A[2] + A[3] + … + A[n])
Al diferenciar la expresión anterior, obtenemos
2nX - 2(A[1] + A[2] + A[3] + … + A[n])
Podemos denotar el término (A[1] + A[2] + A[3] + … + A[n] ) como S. Obtenemos
2nX - 2S
Poniendo 2nX – 2S = 0, obtenemos
X = S/N
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to calculate value of X int valueofX(int ar[], int n) { int sum = 0; for (int i = 0; i < n; i++) { sum = sum + ar[i]; } if (sum % n == 0) { return sum / n; } else { int A = sum / n, B = sum / n + 1; int ValueA = 0, ValueB = 0; // Check for both possibilities for (int i = 0; i < n; i++) { ValueA += (ar[i] - A) * (ar[i] - A); ValueB += (ar[i] - B) * (ar[i] - B); } if (ValueA < ValueB) { return A; } else { return B; } } } // Driver Code int main() { int n = 7; int arr[7] = { 6, 9, 1, 6, 1, 3, 7 }; cout << valueofX(arr, n) << '\n'; return 0; }
Java
// Java implementation of above approach class GFG { // Function to calculate value of X static int valueofX(int ar[], int n) { int sum = 0; for (int i = 0; i < n; i++) { sum = sum + ar[i]; } if (sum % n == 0) { return sum / n; } else { int A = sum / n, B = sum / n + 1; int ValueA = 0, ValueB = 0; // Check for both possibilities for (int i = 0; i < n; i++) { ValueA += (ar[i] - A) * (ar[i] - A); ValueB += (ar[i] - B) * (ar[i] - B); } if (ValueA < ValueB) { return A; } else { return B; } } } // Driver Code public static void main(String args[]) { int n = 7; int arr[] = { 6, 9, 1, 6, 1, 3, 7 }; System.out.println(valueofX(arr, n)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of above approach # Function to calculate value of X def valueofX(ar, n): summ = sum(ar) if (summ % n == 0): return summ // n else: A = summ // n B = summ // n + 1 ValueA = 0 ValueB = 0 # Check for both possibilities for i in range(n): ValueA += (ar[i] - A) * (ar[i] - A) ValueB += (ar[i] - B) * (ar[i] - B) if (ValueA < ValueB): return A else: return B # Driver Code n = 7 arr = [6, 9, 1, 6, 1, 3, 7] print(valueofX(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of above approach using System; class GFG { // Function to calculate value of X static int valueofX(int []ar, int n) { int sum = 0; for (int i = 0; i < n; i++) { sum = sum + ar[i]; } if (sum % n == 0) { return sum / n; } else { int A = sum / n, B = sum / n + 1; int ValueA = 0, ValueB = 0; // Check for both possibilities for (int i = 0; i < n; i++) { ValueA += (ar[i] - A) * (ar[i] - A); ValueB += (ar[i] - B) * (ar[i] - B); } if (ValueA < ValueB) { return A; } else { return B; } } } // Driver Code public static void Main(String []args) { int n = 7; int []arr = { 6, 9, 1, 6, 1, 3, 7 }; Console.WriteLine(valueofX(arr, n)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation of above approach // Function to calculate value of X function valueofX(ar, n) { let sum = 0; for (let i = 0; i < n; i++) { sum = sum + ar[i]; } if (sum % n == 0) { return Math.floor(sum / n); } else { let A = Math.floor(sum / n), B = Math.floor(sum / n + 1); let ValueA = 0, ValueB = 0; // Check for both possibilities for (let i = 0; i < n; i++) { ValueA += (ar[i] - A) * (ar[i] - A); ValueB += (ar[i] - B) * (ar[i] - B); } if (ValueA < ValueB) { return A; } else { return B; } } } // Driver Code let n = 7; let arr = [ 6, 9, 1, 6, 1, 3, 7 ]; document.write(valueofX(arr, n) + "<br>"); // This code is contributed by Surbhi Tyagi. </script>
Producción:
5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)