Given an array arr[] of integers, the task is to find the minimum non-negative integer k such that there exists an index j in the given array such that when arr[j] is updated as arr[j] + k, the sum of elements of an array from index arr[0] to arr[j] is equal to the sum of elements from arr[j + 1] to arr[n – 1] i.e.
arr[0] + arr[1] + … + arr[j] = arr[j + 1] + arr[j + 2] + … + arr[n – 1]
If no such k exists then print -1.
Examples:
Input: arr[] = {6, 7, 1, 3, 8, 2, 4}
Output: 3
If 3 is added to 1 sum of elements from index 0 to 2 and 3 to 6 will be equal to 17.
Input: arr[] = {7, 3}
Output: -1
A simple approach is to run two loops. For every element, find the difference between sums of elements on the left and right. Finally, return the minimum difference between the two sums.
An efficient approach: is to first calculate the prefix sum and store in an array pre[] where pre[i] stores the sum of array elements from arr[0] to arr[i]. For each index, if the sum of elements left to it (including the element itself i.e. pre[i]) is less than or equal to the sum of right elements (pre[n – 1] – pre[i]) then update the value of k as min(k, (pre[n – 1] – pre[i]) – pre[i])
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum value k to be addedint FindMinNum(int arr[], int n){ // Array to store prefix sum int pre[n]; // Initialize the prefix value for first index // as the first element of the array pre[0] = arr[0]; // Compute the prefix sum for rest of the indices for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i]; int k = INT_MAX; for (int i = 0; i < n - 1; i++) { // Sum of elements from arr[i + 1] to arr[n - 1] int rightSum = pre[n - 1] - pre[i]; // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (rightSum >= pre[i]) k = min(k, rightSum - pre[i]); } if (k != INT_MAX) return k; return -1;}// Driver codeint main(){ int arr[] = { 6, 7, 1, 3, 8, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << FindMinNum(arr, n); return 0;} |
Java
// Java implementation of the approach class GfG { // Function to return the minimum value k to be added static int FindMinNum(int arr[], int n) { // Array to store prefix sum int pre[] = new int[n]; // Initialize the prefix value for first index // as the first element of the array pre[0] = arr[0]; // Compute the prefix sum for rest of the indices for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i]; int k = Integer.MAX_VALUE; for (int i = 0; i < n - 1; i++) { // Sum of elements from arr[i + 1] to arr[n - 1] int rightSum = pre[n - 1] - pre[i]; // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (rightSum >= pre[i]) k = Math.min(k, rightSum - pre[i]); } if (k != Integer.MAX_VALUE) return k; return -1; } // Driver code public static void main(String[] args) { int arr[] = { 6, 7, 1, 3, 8, 2, 4 }; int n = arr.length; System.out.println(FindMinNum(arr, n)); }} // This code is contributed by Prerna Saini |
Python3
# Python 3 implementation of the approachimport sys# Function to return the minimum # value k to be addeddef FindMinNum(arr, n): # Array to store prefix sum pre = [0 for i in range(n)] # Initialize the prefix value for first # index as the first element of the array pre[0] = arr[0] # Compute the prefix sum for rest # of the indices for i in range(1, n, 1): pre[i] = pre[i - 1] + arr[i] k = sys.maxsize for i in range(n - 1): # Sum of elements from arr[i + 1] to arr[n - 1] rightSum = pre[n - 1] - pre[i] # If sum on the right side of the ith element # is greater than or equal to the sum on the # left side then update the value of k if (rightSum >= pre[i]): k = min(k, rightSum - pre[i]) if (k != sys.maxsize): return k return -1# Driver codeif __name__ == '__main__': arr = [6, 7, 1, 3, 8, 2, 4] n = len(arr) print(FindMinNum(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach using System;class GfG { // Function to return the minimum value k to be added static int FindMinNum(int []arr, int n) { // Array to store prefix sum int []pre = new int[n]; // Initialize the prefix value for first index // as the first element of the array pre[0] = arr[0]; // Compute the prefix sum for rest of the indices for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i]; int k = int.MaxValue; for (int i = 0; i < n - 1; i++) { // Sum of elements from arr[i + 1] to arr[n - 1] int rightSum = pre[n - 1] - pre[i]; // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (rightSum >= pre[i]) k = Math.Min(k, rightSum - pre[i]); } if (k != int.MaxValue) return k; return -1; } // Driver code public static void Main() { int []arr = { 6, 7, 1, 3, 8, 2, 4 }; int n = arr.Length; Console.WriteLine(FindMinNum(arr, n)); }} // This code is contributed by Ryuga |
PHP
<?php// PHP implementation of the approach// Function to return the minimum // value k to be addedfunction FindMinNum($arr, $n){ // Array to store prefix sum $pre = array(); // Initialize the prefix value for first index // as the first element of the array $pre[0] = $arr[0]; // Compute the prefix sum for // rest of the indices for ($i = 1; $i < $n; $i++) $pre[$i] = $pre[$i - 1] + $arr[$i]; $k = PHP_INT_MAX; for ($i = 0; $i < $n - 1; $i++) { // Sum of elements from arr[i + 1] to arr[n - 1] $rightSum = $pre[$n - 1] - $pre[$i]; // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if ($rightSum >= $pre[$i]) $k = min($k, $rightSum - $pre[$i]); } if ($k != PHP_INT_MAX) return $k; return -1;}// Driver code$arr = array(6, 7, 1, 3, 8, 2, 4);$n = sizeof($arr);echo FindMinNum($arr, $n);// This code is contributed by Akanksha Rai?> |
Javascript
<script>//Javascript Implementation// Function to return the minimum value k to be addedfunction FindMinNum(arr, n){ // Array to store prefix sum var pre = new Array(n); // Initialize the prefix value for first index // as the first element of the array pre[0] = arr[0]; // Compute the prefix sum for rest of the indices for (var i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i]; var k = Number.MAX_VALUE; for (var i = 0; i < n - 1; i++) { // Sum of elements from arr[i + 1] to arr[n - 1] var rightSum = pre[n - 1] - pre[i]; // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (rightSum >= pre[i]) k = Math.min(k, rightSum - pre[i]); } if (k != Number.MAX_VALUE) return k; return -1;}/* Driver code*/var arr = [6, 7, 1, 3, 8, 2, 4];var n = arr.length;document.write(FindMinNum(arr, n))// This code is contributed by shubhamsingh10</script> |
Output
3
Time Complexity : O(n)
Auxiliary Space : O(n)
Further optimization: We can avoid the use of extra space using the below steps.
- First, compute the sum of all the elements and store it in a variable sum.
- Iterate a loop for every index where the left sum at any index can be computed by keep on adding the current elements to the leftsum variable.
- The rightsum can be calculated by keep on subtracting the elements at every index from the sum variable.
- For any ith index if we find that the rightsum is greater than the leftsum then we update the value of k.
Below is the code for the above approach.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum value k to be addedint FindMinNum(int arr[], int n){ int sum = 0; // initialize sum of whole array int leftsum = 0; // initialize leftsum int k = INT_MAX; /* Find sum of the whole array */ for (int i = 0; i < n; ++i) sum += arr[i]; for (int i = 0; i < n; ++i) { sum -= arr[i]; // sum is now right sum for index i leftsum += arr[i]; // add current element to leftsum // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (sum >= leftsum) k = min(k, sum - leftsum); } if (k != INT_MAX) return k; return -1;}// Driver codeint main(){ int arr[] = { 6, 7, 1, 3, 8, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << FindMinNum(arr, n); return 0;}// This code is contributed by Pushpesh raj |
Java
// Java implementation of the approachclass GfG { // Function to return the minimum value k to be added static int FindMinNum(int arr[], int n) { int sum = 0; // initialize sum of whole array int leftsum = 0; // initialize leftsum int k = Integer.MAX_VALUE; /* Find sum of the whole array */ for (int i = 0; i < n; ++i) sum += arr[i]; for (int i = 0; i < n; ++i) { sum -= arr[i]; // sum is now right sum for index // i leftsum += arr[i]; // add current element to leftsum // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (sum >= leftsum) k = Math.min(k, sum - leftsum); } if (k != Integer.MAX_VALUE) return k; return -1; } // Driver code public static void main(String[] args) { int arr[] = { 6, 7, 1, 3, 8, 2, 4 }; int n = arr.length; System.out.println(FindMinNum(arr, n)); }}// This code is contributed by Pushpesh Raj. |
Python3
import sysimport math# Python 3 implementation of the approachclass GfG : # Function to return the minimum value k to be added @staticmethod def FindMinNum( arr, n) : sum = 0 # initialize sum of whole array leftsum = 0 # initialize leftsum k = sys.maxsize # Find sum of the whole array i = 0 while (i < n) : sum += arr[i] i += 1 i = 0 while (i < n) : sum -= arr[i] # sum is now right sum for index # i leftsum += arr[i] # add current element to leftsum # If sum on the right side of the ith element # is greater than or equal to the sum on the # left side then update the value of k if (sum >= leftsum) : k = min(k,sum - leftsum) i += 1 if (k != sys.maxsize) : return k return -1 # Driver code @staticmethod def main( args) : arr = [6, 7, 1, 3, 8, 2, 4] n = len(arr) print(GfG.FindMinNum(arr, n)) if __name__=="__main__": GfG.main([]) # This code is contributed by utkarshshirode02. |
C#
// C# implementation of the approachusing System;class GfG { // Function to return the minimum value k to be added static int FindMinNum(int[] arr, int n) { int sum = 0; // initialize sum of whole array int leftsum = 0; // initialize leftsum int k = int.MaxValue; /* Find sum of the whole array */ for (int i = 0; i < n; ++i) sum += arr[i]; for (int i = 0; i < n; ++i) { sum -= arr[i]; // sum is now right sum for index // i leftsum += arr[i]; // add current element to leftsum // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (sum >= leftsum) k = Math.Min(k, sum - leftsum); } if (k != int.MaxValue) return k; return -1; } // Driver code public static void Main() { int[] arr = { 6, 7, 1, 3, 8, 2, 4 }; int n = arr.Length; Console.WriteLine(FindMinNum(arr, n)); }}// This code is contributed by Pushpesh Raj |
Javascript
<script>//Javascript Implementation// Function to return the minimum value k to be addedfunction FindMinNum(arr, n){ var sum = 0; // initialize sum of whole array var leftsum = 0; // initialize leftsum var k = Number.MAX_VALUE; /* Find sum of the whole array */ for (var i = 0; i < n; ++i) sum += arr[i]; for (var i = 0; i < n; ++i) { sum -= arr[i]; // sum is now right sum for index i leftsum+=arr[i]; // add current element to leftsum // If sum on the right side of the ith element // is greater than or equal to the sum on the // left side then update the value of k if (sum >= leftsum) k = Math.min(k, sum - leftsum); } if (k != Number.MAX_VALUE) return k; return -1;}/* Driver code*/var arr = [6, 7, 1, 3, 8, 2, 4];var n = arr.length;document.write(FindMinNum(arr, n))// This code is contributed by Pushpesh raj</script> |
Output
3
The idea is similar to optimized solution of equilibrium index problem.
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!
