Given an Array arr[] or N elements, the task is to minimize the sum of squares of difference of adjacent elements by adding one element at any position of the array.
Examples:
Input: N = 4, arr = [4, 7, 1, 4]
Output: 36
Explanation: The sum of squares of difference of adjacent element before inserting any element is (4-7)^2 + (7-1)^2 + (1-4)^2 = 9+36+9 = 54. After insertion 4 in between 7 and 1 array become
arr = [4, 7, 4, 1, 4] and sum of square of adjacent element will become 9+9+9+9 = 36.Input:- N = 4, arr = [3, 5, 1, 8]
Output: 45
Explanation:-Sum of squares of differences of adjacent elements before insertion is 4+16+49 = 69. After insertion 4 in between 1 and 8 the array will become arr = [3, 5, 1, 4, 8] the sum will become 4+16+9+16 = 45. That is the minimum sum which you can make.
Approach: To solve the problem follow the below observations:
- So first of all we have to observe that we are adding the sum of squares of differences of adjacent elements, so to minimize we need to minimize the maximum square so that answer will get more minimized.
- We will check for all adjacent element differences and find the maximum difference so that we can minimize it.
- After it, we will add an element between the elements which are forming the maximum square.
- We will add the element which is close to both the elements if we have to add an element in (1, 9) then we will add 5. So the difference of 1, 5 will be 4 and of 5, 9 will be 4.
- And if we have to add an element in between elements in which the difference is odd then we will do that like this If we have to add between (1, 8) then we will add 5 or 4. Because of we add 5 then the difference between (1, 5) will be 4 and (5, 8) will be 3, If we add 4 then the difference between (1, 4) is 3, and between (4, 8) will be 4. So we can add either 4 or 5.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find minimum sumint minimumSum(int n, vector<int> arr){ // To store answer long long ans = 0; // To store maximum difference // between to adjacent elements int diff = 0; // Iterating over array for (int i = 1; i < n; i++) { // Sqaure of current adjacent // element difference long long temp = pow(abs(arr[i] - arr[i - 1]), 2); // Adding to answer ans += temp; // Taking maximum difference diff = max(diff, abs(arr[i] - arr[i - 1])); } // Difference of elements // in between element adding // after adding element int one = diff / 2, two = diff / 2; // If diff is odd if (diff % 2) { two++; } long long t = pow(one, 2) + pow(two, 2); t = pow(diff, 2) - t; // Decresing the sum after adding element ans -= t; return ans;}// Driver codeint main(){ int N = 4; vector<int> arr = { 4, 7, 1, 4 }; // Function call cout << minimumSum(N, arr); return 0;} |
Java
// JAVA code for the above approach:import java.util.*;public class GFG { // Function to find minimum sum public static long minimumSum(int n, List<Integer> arr) { // To store answer long ans = 0; // To store maximum difference between two adjacent // elements int diff = 0; // Iterating over array for (int i = 1; i < n; i++) { // Square of current adjacent element difference long temp = (long)Math.pow( Math.abs(arr.get(i) - arr.get(i - 1)), 2); // Adding to answer ans += temp; // Taking maximum difference diff = Math.max( diff, Math.abs(arr.get(i) - arr.get(i - 1))); } // Difference of elements in between element adding // after adding element int one = diff / 2, two = diff / 2; // If diff is odd if (diff % 2 != 0) { two++; } long t = (long)Math.pow(one, 2) + (long)Math.pow(two, 2); t = (long)Math.pow(diff, 2) - t; // Decreasing the sum after adding element ans -= t; return ans; } // Driver code public static void main(String[] args) { int N = 4; List<Integer> arr = new ArrayList<>(Arrays.asList(4, 7, 1, 4)); // Function call System.out.println(minimumSum(N, arr)); }}// This code is contributed by rambabuguphka |
Python3
# Python3 code for the above approach:# Function to find minimum sumdef minimumSum(n, arr): # To store answer ans = 0 # To store maximum difference # between two adjacent elements diff = 0 # Iterating over array for i in range(1, n): # Square of current adjacent # element difference temp = pow(abs(arr[i] - arr[i - 1]), 2) # Adding to answer ans += temp # Taking maximum difference diff = max(diff, abs(arr[i] - arr[i - 1])) # Difference of elements # in between element adding # after adding element one = diff // 2 two = diff // 2 # If diff is odd if diff % 2: two += 1 t = pow(one, 2) + pow(two, 2) t = pow(diff, 2) - t # Decreasing the sum after adding element ans -= t return ans# Driver codeif __name__ == "__main__": N = 4 arr = [4, 7, 1, 4] # Function call print(minimumSum(N, arr))# This code is contributed by rambabuguphka |
C#
using System;using System.Collections.Generic;class GFG { // Function to find minimum sum static long MinimumSum(int n, List<int> arr) { // To store answer long ans = 0; // To store maximum difference between two adjacent // elements int diff = 0; // Iterating over array for (int i = 1; i < n; i++) { // Square of current adjacent element difference long temp = (long)Math.Pow( Math.Abs(arr[i] - arr[i - 1]), 2); // Adding to answer ans += temp; // Taking maximum difference diff = Math.Max(diff, Math.Abs(arr[i] - arr[i - 1])); } // Difference of elements in between element adding // after adding element int one = diff / 2, two = diff / 2; // If diff is odd if (diff % 2 != 0) { two++; } long t = (long)Math.Pow(one, 2) + (long)Math.Pow(two, 2); t = (long)Math.Pow(diff, 2) - t; // Decreasing the sum after adding element ans -= t; return ans; } static void Main(string[] args) { int N = 4; List<int> arr = new List<int>{ 4, 7, 1, 4 }; // Function call Console.WriteLine(MinimumSum(N, arr)); }}// This code is contributed by shivamgupta0987654321 |
Javascript
// Function to find minimum sumfunction minimumSum(n, arr) { // To store answer let ans = 0; // To store maximum difference // between two adjacent elements let diff = 0; // Iterating over the array for (let i = 1; i < n; i++) { // Square of the current adjacent // element difference let temp = Math.pow(Math.abs(arr[i] - arr[i - 1]), 2); // Adding to the answer ans += temp; // Taking the maximum difference diff = Math.max(diff, Math.abs(arr[i] - arr[i - 1])); } // Difference of elements // in between elements adding // after adding elements let one = Math.floor(diff / 2); let two = Math.floor(diff / 2); // If diff is odd if (diff % 2 === 1) { two++; } let t = Math.pow(one, 2) + Math.pow(two, 2); t = Math.pow(diff, 2) - t; // Decreasing the sum after adding element ans -= t; return ans;}// Driver codeconst N = 4;const arr = [4, 7, 1, 4];// Function callconsole.log(minimumSum(N, arr));// Contributed by Aditi Tyagi |
Output
36
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
