Given an array A[] consisting of N integers(1-based indexing), the task is to find the minimum value of the function ![\sum_{i = 1}^{N}(A[i] - (X + i))](https://cdn.geeksforgeeks.org/static/gallery/images/logo.png "Rendered by QuickLaTeX.com"){kind=logo}
for any possible value of X.
Examples:
Input: A[] = {1, 2, 3, 4}
Output: 0
Explanation:
Consider the value of X as 0, then the value of the given function is (1 – 1 + 2 – 2 + 3 – 3 + 4 – 4) = 0, which is minimum.Input: A[] = {5, 3, 9}
Output: 5
Approach: The given problem can be solved based on the following observations:
- Consider a function as (B[i] = A[i] ? i), then to minimize the value of
![\sum_{i = 1}^{N}(B[i] - X)](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20181%2033'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
, the idea is to choose the value of X as the median of the array B[] such that the sum is minimized.
Follow the steps to solve the problem:
- Initialize an array, say B[] that stores the value of (A[i] – i) for every possible value of the array A[].
- Traverse the given array A[] and for each index i, update the value of B[i] as (A[i] – i).
- Sort the array B[] in ascending order and find the value X as the median of the array B[].
- After completing the above steps, find the value of the given function
![\sum_{i = 1}^{N}(A[i] - (X + i))](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20241%2033'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
for the calculated value of X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum value of// the given functionint minimizeFunction(int A[], int N){ // Stores the value of A[i] - i int B[N]; // Traverse the given array A[] for (int i = 0; i < N; i++) { // Update the value of B[i] B[i] = A[i] - i - 1; } // Sort the array B[] sort(B, B + N); // Calculate the median of the // array B[] int median = (B[int(floor((N - 1) / 2.0))] + B[int(ceil((N - 1) / 2.0))]) / 2; // Stores the minimum value of // the function int minValue = 0; for (int i = 0; i < N; i++) { // Update the minValue minValue += abs(A[i] - (median + i + 1)); } // Return the minimum value return minValue;}// Driver Codeint main(){ int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int N = sizeof(A) / sizeof(A[0]); cout << minimizeFunction(A, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.lang.Math;import java.util.*;class GFG { public static int minimizeFunction(int A[], int N) { // Stores the value of A[i] - i int B[] = new int[N]; // Traverse the given array A[] for (int i = 0; i < N; i++) { // Update the value of B[i] B[i] = A[i] - i - 1; } // Sort the array B[] Arrays.sort(B); // Calculate the median of the // array B[] int median = (B[(int)(Math.floor((N - 1) / 2.0))] + B[(int)(Math.ceil((N - 1) / 2.0))]) / 2; // Stores the minimum value of // the function int minValue = 0; for (int i = 0; i < N; i++) { // Update the minValue minValue += Math.abs(A[i] - (median + i + 1)); } // Return the minimum value return minValue; } public static void main(String[] args) { int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int N = A.length; System.out.println(minimizeFunction(A, N)); }}// This code is contributed by sam_2200. |
Python3
# Python3 program for the above approachfrom math import floor, ceil# Function to find minimum value of# the given functiondef minimizeFunction(A, N): # Stores the value of A[i] - i B = [0] * N # Traverse the given array A[] for i in range(N): # Update the value of B[i] B[i] = A[i] - i - 1 # Sort the array B[] B = sorted(B) # Calculate the median of the # array B[] x, y = int(floor((N - 1) / 2.0)), int(ceil((N - 1) / 2.0)) median = (B[x] + B[y]) / 2 # Stores the minimum value of # the function minValue = 0 for i in range(N): # Update the minValue minValue += abs(A[i] - (median + i + 1)) # Return the minimum value return int(minValue)# Driver Codeif __name__ == '__main__': A = [1, 2, 3, 4, 5, 6, 7, 8, 9] N = len(A) print(minimizeFunction(A, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG { public static int minimizeFunction(int[] A, int N) { // Stores the value of A[i] - i int[] B = new int[N]; // Traverse the given array A[] for (int i = 0; i < N; i++) { // Update the value of B[i] B[i] = A[i] - i - 1; } // Sort the array B[] Array.Sort(B); // Calculate the median of the // array B[] int median = (B[(int)(Math.Floor((N - 1) / 2.0))] + B[(int)(Math.Ceiling((N - 1) / 2.0))]) / 2; // Stores the minimum value of // the function int minValue = 0; for (int i = 0; i < N; i++) { // Update the minValue minValue += Math.Abs(A[i] - (median + i + 1)); } // Return the minimum value return minValue; } static void Main() { int []A = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int N = A.Length; Console.WriteLine(minimizeFunction(A, N)); }}// This code is contributed by SoumikMondal. |
Javascript
<script>// Javascript program for the above approachfunction minimizeFunction(A, N){ // Stores the value of A[i] - i let B = Array.from({length: N}, (_, i) => 0); // Traverse the given array A[] for (let i = 0; i < N; i++) { // Update the value of B[i] B[i] = A[i] - i - 1; } // Sort the array B[] B.sort(); // Calculate the median of the // array B[] let median = (B[(Math.floor((N - 1) / 2.0))] + B[(Math.ceil((N - 1) / 2.0))]) / 2; // Stores the minimum value of // the function let minValue = 0; for (let i = 0; i < N; i++) { // Update the minValue minValue += Math.abs(A[i] - (median + i + 1)); } // Return the minimum value return minValue; }// Driver Code let A = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; let N = A.length; document.write(minimizeFunction(A, N));</script> |
Output:
0
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
