Минимальное значение, добавляемое к arr [i], чтобы массив можно было разделить по индексу i с равной суммой
Для данного массива целых чисел arr [] задача состоит в том, чтобы найти минимальное неотрицательное целое число k такое, что существует индекс j в данном массиве, такой, что когда arr [j] обновляется как arr [j] + k , сумма элементов массива от arr [0] до arr [j] равна сумме элементов от arr [j + 1] до arr [n - 1], т.е.
arr[0] + arr[1] + … + arr[j] = arr[j + 1] + arr[j + 2] + … + arr[n – 1]
.
Если такого k не существует, выведите -1 .
Примеры:
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 left and right. Finally, return 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 approachclass GfG{// Function to return the minimum value k to be addedstatic 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 codepublic 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 approachusing 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> |
3
Сложность времени: O (n)
Вспомогательное пространство: O (n)
Дальнейшая оптимизация: мы можем избежать использования лишнего пространства, используя следующие шаги.
1) Вычислить сумму всех элементов.
2) Продолжайте складывать левую сумму, и правая сумма может быть получена путем вычитания левой суммы из общей суммы.
Идея аналогична оптимизированному решению проблемы индекса равновесия.
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.