Dada una array arr[] de N elementos, la tarea es actualizar todos los elementos de la array de modo que un elemento arr[i] se actualice como arr[i] = arr[i] – X donde X = arr[i + 1] + arr[i + 2] + … + arr[N – 1] y finalmente imprima la suma de la array actualizada.
Ejemplos:
Entrada: arr[] = {40, 25, 12, 10}
Salida: 8
La array actualizada será {-7, 3, 2, 10}.
-7 + 3 + 2 + 10 = 8
Entrada: arr[] = {50, 30, 10, 2, 0}
Salida: 36
Enfoque: una solución simple es para cada valor posible de i, actualizar arr[i] = arr[i] – sum(arr[i+1…N-1]).
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Utility function to return
// the sum of the array
int sumArr(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
int sumModArr(int arr[], int n)
{
for (int i = 0; i < n - 1; i++) {
// Find the sum of the subarray
// arr[i+1...n-1]
int subSum = 0;
for (int j = i + 1; j < n; j++) {
subSum += arr[j];
}
// Subtract the subarray sum
arr[i] -= subSum;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
int main()
{
int arr[] = { 40, 25, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << sumModArr(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Utility function to return
// the sum of the array
static int sumArr(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
static int sumModArr(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
// Find the sum of the subarray
// arr[i+1...n-1]
int subSum = 0;
for (int j = i + 1; j < n; j++)
{
subSum += arr[j];
}
// Subtract the subarray sum
arr[i] -= subSum;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
public static void main(String []args)
{
int arr[] = { 40, 25, 12, 10 };
int n = arr.length;
System.out.println(sumModArr(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Utility function to return # the sum of the array def sumArr(arr, n): sum = 0 for i in range(n): sum += arr[i] return sum # Function to return the sum # of the modified array def sumModArr(arr, n): for i in range(n - 1): # Find the sum of the subarray # arr[i+1...n-1] subSum = 0 for j in range(i + 1, n): subSum += arr[j] # Subtract the subarray sum arr[i] -= subSum # Return the sum of # the modified array return sumArr(arr, n) # Driver code arr = [40, 25, 12, 10] n = len(arr) print(sumModArr(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to return
// the sum of the array
static int sumArr(int []arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
static int sumModArr(int []arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
// Find the sum of the subarray
// arr[i+1...n-1]
int subSum = 0;
for (int j = i + 1; j < n; j++)
{
subSum += arr[j];
}
// Subtract the subarray sum
arr[i] -= subSum;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
public static void Main()
{
int []arr = { 40, 25, 12, 10 };
int n = arr.Length;
Console.WriteLine(sumModArr(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Utility function to return
// the sum of the array
function sumArr(arr , n) {
var sum = 0;
for (i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
function sumModArr(arr , n) {
for (i = 0; i < n - 1; i++) {
// Find the sum of the subarray
// arr[i+1...n-1]
var subSum = 0;
for (j = i + 1; j < n; j++) {
subSum += arr[j];
}
// Subtract the subarray sum
arr[i] -= subSum;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
var arr = [ 40, 25, 12, 10 ];
var n = arr.length;
document.write(sumModArr(arr, n));
// This code is contributed by todaysgaurav
</script>
Producción:
8
Complejidad del tiempo: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: una solución eficiente es atravesar el arreglo desde el final para que la suma del subarreglo hasta ahora, es decir , la suma (arr[i+1…n-1]) se pueda usar para calcular el suma del subarreglo actual arr[i…n-1] ie sum(arr[i…n-1]) = arr[i] + sum(arr[i+1…n-1]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Utility function to return
// the sum of the array
int sumArr(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
int sumModArr(int arr[], int n)
{
int subSum = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
int curr = arr[i];
// Subtract the subarray sum
arr[i] -= subSum;
// Sum of subarray arr[i...n-1]
subSum += curr;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
int main()
{
int arr[] = { 40, 25, 12, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << sumModArr(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Utility function to return
// the sum of the array
static int sumArr(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
static int sumModArr(int arr[], int n)
{
int subSum = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
{
int curr = arr[i];
// Subtract the subarray sum
arr[i] -= subSum;
// Sum of subarray arr[i...n-1]
subSum += curr;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
public static void main (String[] args)
{
int []arr = { 40, 25, 12, 10 };
int n = arr.length;
System.out.println(sumModArr(arr, n));
}
}
// This code is contributed by kanugargng
Python3
# Python3 implementation of the approach # Utility function to return # the sum of the array def sumArr(arr, n): sum = 0; for i in range(n): sum += arr[i]; return sum; # Function to return the sum # of the modified array def sumModArr(arr, n): subSum = arr[n - 1]; for i in range(n - 2, -1, -1): curr = arr[i]; # Subtract the subarray sum arr[i] -= subSum; # Sum of subarray arr[i...n-1] subSum += curr; # Return the sum of # the modified array return sumArr(arr, n); # Driver code arr = [40, 25, 12, 10 ]; n = len(arr); print(sumModArr(arr, n)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to return
// the sum of the array
static int sumArr(int []arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
static int sumModArr(int []arr, int n)
{
int subSum = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
{
int curr = arr[i];
// Subtract the subarray sum
arr[i] -= subSum;
// Sum of subarray arr[i...n-1]
subSum += curr;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
public static void Main (String[] args)
{
int []arr = { 40, 25, 12, 10 };
int n = arr.Length;
Console.WriteLine(sumModArr(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Utility function to return
// the sum of the array
function sumArr(arr, n) {
var sum = 0;
for (var i = 0; i < n; i++) sum += arr[i];
return sum;
}
// Function to return the sum
// of the modified array
function sumModArr(arr, n) {
var subSum = arr[n - 1];
for (var i = n - 2; i >= 0; i--) {
var curr = arr[i];
// Subtract the subarray sum
arr[i] -= subSum;
// Sum of subarray arr[i...n-1]
subSum += curr;
}
// Return the sum of
// the modified array
return sumArr(arr, n);
}
// Driver code
var arr = [40, 25, 12, 10];
var n = arr.length;
document.write(sumModArr(arr, n));
// This code is contributed by rdtank.
</script>
Producción:
8
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por RishavSinghMehta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA