Given an array arr[] of N elements, the task is to find the value of x that minimizes the value of expression for c = 1.
|a1−x|c+|a2−x|c+···+|an−x|c = |a1−x|+|a2−x|+···+|an−x|
Examples:
Input: arr[] = { 1, 2, 9, 2, 6 }
Output: 2
Explanation: The best solution is to select x = 2 which produces the sum |1−2| + |2−2| + |9−2| + |2−2| + |6−2| = 12 , which is the minimum possible sum, for all other values, the sum so obtained will be greater than 2Input: arr[] = { 1, 2, 3, 4, 5 }
Output: 3
Approach: In the general case, the best choice for x is the median of the given numbers, The median is an optimal choice, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger than the median, the sum becomes smaller by decreasing x. Hence, the optimal solution is that x is the median.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the possible // values of x that minimizes the sum void findX(int arr[], int n) { // Sort the numbers sort(arr, arr + n); // Stores the median int x; // Only one median if n is odd if (n % 2 != 0) { x = arr[n / 2]; } // Two medians if n is even // and every value between them // is optimal print any of them else { int a = arr[n / 2 - 1]; int b = arr[n / 2]; x = a; } int sum = 0; // Find minimum sum for (int i = 0; i < n; i++) { sum += abs(arr[i] - x); } cout << sum; } // Driver Code int main() { int arr1[] = { 1, 2, 9, 2, 6 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); findX(arr1, n1); return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { // Function to print the possible // values of x that minimizes the sum static void findX(int arr[], int n) { // Sort the numbers Arrays.sort(arr); // Stores the median int x; // Only one median if n is odd if (n % 2 != 0) { x = arr[(int)Math.floor(n / 2)]; } // Two medians if n is even // and every value between them // is optimal print any of them else { int a = arr[n / 2 - 1]; int b = arr[n / 2]; x = a; } int sum = 0; // Find minimum sum for (int i = 0; i < n; i++) { sum += Math.abs(arr[i] - x); } System.out.println( sum); } public static void main (String[] args) { int arr1[] = { 1, 2, 9, 2, 6 }; int n1 = arr1.length; findX(arr1, n1); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to print the possible # values of x that minimizes the sum def findX(arr, n): # Sort the numbers arr.sort(); # Stores the median x = None; # Only one median if n is odd if (n % 2 != 0): x = arr[n // 2]; # Two medians if n is even # and every value between them # is optimal print any of them else: a = arr[(n // 2) - 1]; b = arr[n // 2]; x = a; sum = 0; # Find minimum sum for i in range(n): sum += abs(arr[i] - x); print(sum); # Driver Code arr1 = [1, 2, 9, 2, 6]; n1 = len(arr1) findX(arr1, n1); # This code is contributed by gfgking. |
C#
// C# code for the above approach using System; class GFG { // Function to print the possible // values of x that minimizes the sum static void findX(int[] arr, int n) { // Sort the numbers Array.Sort(arr); // Stores the median int x; // Only one median if n is odd if (n % 2 != 0) { x = arr[(int)Math.Floor((float)(n / 2))]; } // Two medians if n is even // and every value between them // is optimal print any of them else { int a = arr[n / 2 - 1]; x = a; } int sum = 0; // Find minimum sum for (int i = 0; i < n; i++) { sum += Math.Abs(arr[i] - x); } Console.WriteLine(sum); } public static void Main(string[] args) { int[] arr1 = { 1, 2, 9, 2, 6 }; int n1 = arr1.Length; findX(arr1, n1); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to print the possible // values of x that minimizes the sum function findX(arr, n) { // Sort the numbers arr.sort((a, b) => a - b); // Stores the median let x; // Only one median if n is odd if (n % 2 != 0) { x = arr[(Math.floor(n / 2))]; } // Two medians if n is even // and every value between them // is optimal print any of them else { let a = arr[(Math.floor(n / 2) - 1)]; let b = arr[(Math.floor(n / 2))]; x = a; } let sum = 0; // Find minimum sum for (let i = 0; i < n; i++) { sum += Math.abs(arr[i] - x); } document.write(sum); } // Driver Code let arr1 = [1, 2, 9, 2, 6]; let n1 = arr1.length; findX(arr1, n1); // This code is contributed by gfgking. </script> |
12
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Given an array arr[] of N elements, the task is to find the value of x that minimizes the value of expression for c = 2.
|a1−x|c+|a2−x|c+···+|an−x|c = (a1−x)2+(a2−x)2+···+(an−x)2.
Examples :
Input: arr[] = { 1, 2, 9, 2, 6 }
Output: 4
Explanation: The best solution is to select x = 4 which produces the sum (1−4)^2 + (2−4)^2 + (9−4)^2 + (2−4)^2 + (6−4)^2 = 46, which is the minimum possible sum.Input: arr[] = { 1, 2, 2, 4, 6 }
Output: 3
Approach: In the general case, the best choice for x is the average of the numbers. This result can be derived by expanding the sum as follows:
nx2−2x(a1+a2+···+an) + (a12+a22+···+an2)
The last part does not depend on x. The remaining parts form a function nx2 − 2xs where s=a1+a2+···+an. Applying derivative to this equation w.r.t x and equating the result to zero gives us x = s / n, which is the value that minimizes the sum.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the value of x // that minimizes the sum void findX(int arr[], int n) { // Store the sum double sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // Store the average of numbers double x = sum / n; double minSum = 0; // Find minimum sum for (int i = 0; i < n; i++) { minSum += pow((arr[i] - x), 2); } cout << minSum; } // Driver Code int main() { int arr[] = { 1, 2, 9, 2, 6 }; int n = sizeof(arr) / sizeof(arr[0]); findX(arr, n); return 0; } |
Java
// Java implementation for the above approach import java.util.*; public class GFG { // Function to find the value of x // that minimizes the sum static void findX(int []arr, int n) { // Store the sum int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // Store the average of numbers int x = sum / n; int minSum = 0; // Find minimum sum for (int i = 0; i < n; i++) { minSum += Math.pow((arr[i] - x), 2); } System.out.print(minSum); } // Driver Code public static void main(String args[]) { int []arr = { 1, 2, 9, 2, 6 }; int n = arr.length; findX(arr, n); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python implementation for the above approach # Function to find the value of x # that minimizes the sum def findX(arr, n): # Store the sum sum = 0; for i in range(n): sum += arr[i]; # Store the average of numbers x = sum // n; minSum = 0; # Find minimum sum for i in range(n): minSum += pow((arr[i] - x), 2); print(minSum); # Driver Code if __name__ == '__main__': arr = [ 1, 2, 9, 2, 6 ]; n = len(arr); findX(arr, n); # This code is contributed by shikhasingrajput |
C#
// C# implementation for the above approach using System; class GFG { // Function to find the value of x // that minimizes the sum static void findX(int []arr, int n) { // Store the sum int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // Store the average of numbers int x = sum / n; int minSum = 0; // Find minimum sum for (int i = 0; i < n; i++) { minSum += (int)Math.Pow((arr[i] - x), 2); } Console.Write(minSum); } // Driver Code public static void Main() { int []arr = { 1, 2, 9, 2, 6 }; int n = arr.Length; findX(arr, n); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript implementation for the above approach // Function to find the value of x // that minimizes the sum function findX(arr, n) { // Store the sum let sum = 0; for (let i = 0; i < n; i++) { sum += arr[i]; } // Store the average of numbers let x = sum / n; let minSum = 0; // Find minimum sum for (let i = 0; i < n; i++) { minSum += Math.pow((arr[i] - x), 2); } document.write(minSum); } // Driver Code let arr = [ 1, 2, 9, 2, 6 ]; let n = arr.length; findX(arr, n); // This code is contributed by Samim Hossain Mondal. </script> |
46
Time Complexity: O(N)
Auxiliary Space: O(1)
