Dado un arreglo arr[] de n enteros, construya un Sum Array sum[] (del mismo tamaño) tal que sum[i] sea igual a la suma de todos los elementos de arr[] excepto arr[i]. Resuélvelo sin operador de resta y en O(n).
Ejemplos:
Entrada: arr[] = {3, 6, 4, 8, 9}
Salida: sum[] = {27, 24, 26, 22, 21}Entrada: arr[] = {4, 5, 7, 3, 10, 1}
Salida: sum[] = {26, 25, 23, 27, 20, 29}
Algoritmo:
1) Construya una array temporal leftSum[] tal que leftSum[i] contenga la suma de todos los elementos a la izquierda de arr[i] excluyendo arr[i].
2) Construya otra array temporal rightSum[] tal que rightSum[i] contenga la suma de todos los elementos a la derecha de arr[i] excluyendo arr[i].
3) Para obtener sum[], sum left[] y right[].
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
void sumArray(int arr[], int n)
{
/* Allocate memory for temporary arrays leftSum[],
rightSum[] and Sum[]*/
int leftSum[n], rightSum[n], Sum[n], i, j;
/* Left most element of left array is always 0 */
leftSum[0] = 0;
/* Rightmost most element of right
array is always 0 */
rightSum[n - 1] = 0;
/* Construct the left array*/
for (i = 1; i < n; i++)
leftSum[i] = arr[i - 1] + leftSum[i - 1];
/* Construct the right array*/
for (j = n - 2; j >= 0; j--)
rightSum[j] = arr[j + 1] + rightSum[j + 1];
/* Construct the sum array using
left[] and right[] */
for (i = 0; i < n; i++)
Sum[i] = leftSum[i] + rightSum[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
cout << Sum[i] << " ";
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 3, 6, 4, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
sumArray(arr, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class Geeks {
public static void sumArray(int arr[], int n)
{
/* Allocate memory for temporary arrays
leftSum[], rightSum[] and Sum[]*/
int leftSum[] = new int[n];
int rightSum[] = new int[n];
int Sum[] = new int[n];
int i = 0, j = 0;
/* Left most element of left array is
always 0 */
leftSum[0] = 0;
/* Right most element of right array
is always 0 */
rightSum[n - 1] = 0;
/* Construct the left array*/
for (i = 1; i < n; i++)
leftSum[i] = arr[i - 1] + leftSum[i - 1];
/* Construct the right array*/
for (j = n - 2; j >= 0; j--)
rightSum[j] = arr[j + 1] + rightSum[j + 1];
/* Construct the sum array using
left[] and right[] */
for (i = 0; i < n; i++)
Sum[i] = leftSum[i] + rightSum[i];
/*print the sum array*/
for (i = 0; i < n; i++)
System.out.print(Sum[i] + " ");
}
/* Driver function to test above function*/
public static void main(String[] args)
{
int arr[] = { 3, 6, 4, 8, 9 };
int n = arr.length;
sumArray(arr, n);
}
}
Python3
# Python3 implementation of above approach def sumArray(arr, n): # Allocate memory for temporary arrays # leftSum[], rightSum[] and Sum[] leftSum = [0 for i in range(n)] rightSum = [0 for i in range(n)] Sum = [0 for i in range(n)] i, j = 0, 0 # Left most element of left # array is always 0 leftSum[0] = 0 # Rightmost most element of right # array is always 0 rightSum[n - 1] = 0 # Construct the left array for i in range(1, n): leftSum[i] = arr[i - 1] + leftSum[i - 1] # Construct the right array for j in range(n - 2, -1, -1): rightSum[j] = arr[j + 1] + rightSum[j + 1] # Construct the sum array using # left[] and right[] for i in range(0, n): Sum[i] = leftSum[i] + rightSum[i] # print the constructed prod array for i in range(n): print(Sum[i], end = " ") # Driver Code arr = [3, 6, 4, 8, 9] n = len(arr) sumArray(arr, n) # This code is contributed by # mohit kumar 29
C#
// C# implementation of above approach
using System ;
class Geeks {
public static void sumArray(int []arr, int n)
{
/* Allocate memory for temporary arrays
leftSum[], rightSum[] and Sum[]*/
int []leftSum = new int[n];
int []rightSum = new int[n];
int []Sum = new int[n];
int i = 0, j = 0;
/* Left most element of left array is
always 0 */
leftSum[0] = 0;
/* Right most element of right array
is always 0 */
rightSum[n - 1] = 0;
/* Construct the left array*/
for (i = 1; i < n; i++)
leftSum[i] = arr[i - 1] + leftSum[i - 1];
/* Construct the right array*/
for (j = n - 2; j >= 0; j--)
rightSum[j] = arr[j + 1] + rightSum[j + 1];
/* Construct the sum array using
left[] and right[] */
for (i = 0; i < n; i++)
Sum[i] = leftSum[i] + rightSum[i];
/*print the sum array*/
for (i = 0; i < n; i++)
Console.Write(Sum[i] + " ");
}
/* Driver function to test above function*/
public static void Main()
{
int []arr = { 3, 6, 4, 8, 9 };
int n = arr.Length;
sumArray(arr, n);
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP implementation of above approach
function sumArray($arr, $n)
{
/* Allocate memory for temporary
arrays leftSum[], rightSum[] and Sum[]*/
$leftSum = array_fill(0, $n, 0);
$rightSum = array_fill(0, $n, 0);
$Sum = array_fill(0, $n, 0);
/* Left most element of left
array is always 0 */
$leftSum[0] = 0;
/* Rightmost most element of right
array is always 0 */
$rightSum[$n - 1] = 0;
/* Construct the left array*/
for ($i = 1; $i < $n; $i++)
$leftSum[$i] = $arr[$i - 1] +
$leftSum[$i - 1];
/* Construct the right array*/
for ($j = $n - 2; $j >= 0; $j--)
$rightSum[$j] = $arr[$j + 1] +
$rightSum[$j + 1];
/* Construct the sum array using
left[] and right[] */
for ($i = 0; $i < $n; $i++)
$Sum[$i] = $leftSum[$i] + $rightSum[$i];
/* print the constructed prod array */
for ($i = 0; $i < $n; $i++)
echo $Sum[$i]." ";
}
// Driver Code
$arr = array( 3, 6, 4, 8, 9 );
$n = count($arr);
sumArray($arr, $n);
// This code is contributed
// by chandan_jnu
?>
Javascript
<script>
// JavaScript implementation of above approach
function sumArray(arr, n)
{
/* Allocate memory for temporary arrays
leftSum[], rightSum[] and Sum[]*/
let leftSum = new Array(n);
let rightSum = new Array(n);
let Sum = new Array(n);
let i = 0, j = 0;
/* Left most element of left array is
always 0 */
leftSum[0] = 0;
/* Right most element of right array
is always 0 */
rightSum[n - 1] = 0;
/* Construct the left array*/
for (i = 1; i < n; i++)
leftSum[i] = arr[i - 1] + leftSum[i - 1];
/* Construct the right array*/
for (j = n - 2; j >= 0; j--)
rightSum[j] = arr[j + 1] + rightSum[j + 1];
/* Construct the sum array using
left[] and right[] */
for (i = 0; i < n; i++)
Sum[i] = leftSum[i] + rightSum[i];
/*print the sum array*/
for (i = 0; i < n; i++)
document.write(Sum[i] + " ");
}
let arr = [ 3, 6, 4, 8, 9 ];
let n = arr.length;
sumArray(arr, n);
</script>
Producción:
27 24 26 22 21
Complejidad de Tiempo: O(n)
Complejidad de Espacio: O(n)
Espacio Auxiliar: O(n)
El método anterior se puede optimizar para trabajar en el espacio auxiliar O(1).
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
void sumArray(int arr[], int n)
{
int i, temp = 0;
/* Allocate memory for the sum array */
int Sum[n];
/* Initialize the sum array as 0 */
memset(Sum, 0, n);
/* In this loop, temp variable contains
sum of elements on left side excluding
arr[i] */
for (i = 0; i < n; i++) {
Sum[i] = temp;
temp += arr[i];
}
/* Initialize temp to 0 for sum on right
side */
temp = 0;
/* In this loop, temp variable contains
sum of elements on right side excluding
arr[i] */
for (i = n - 1; i >= 0; i--) {
Sum[i] += temp;
temp += arr[i];
}
for (i = 0; i < n; i++)
cout << Sum[i] << " ";
}
/* Driver program to test above function */
int main()
{
int arr[] = { 3, 6, 4, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
sumArray(arr, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class Geeks {
public static void sumArray(int arr[], int n)
{
int i = 0, temp = 0;
int Sum[] = new int[n];
Arrays.fill(Sum, 0);
/* In this loop, temp variable contains
sum of elements on left side excluding
arr[i] */
for (i = 0; i < n; i++) {
Sum[i] = temp;
temp += arr[i];
}
/* Initialize temp to 0 for sum on right side */
temp = 0;
/* In this loop, temp variable contains
sum of elements on right side excluding
arr[i] */
for (i = n - 1; i >= 0; i--) {
Sum[i] += temp;
temp += arr[i];
}
for (i = 0; i < n; i++)
System.out.print(Sum[i] + " ");
}
/* Driver function to test above function*/
public static void main(String[] args)
{
int arr[] = { 3, 6, 4, 8, 9 };
int n = arr.length;
sumArray(arr, n);
}
}
Python3
# Python3 implementation of above approach def sumArray(arr, n): i, temp = 0, 0 # Allocate memory for the sum array */ Sum = [0 for i in range(n)] '''In this loop, temp variable contains sum of elements on left side excluding arr[i] ''' for i in range(n): Sum[i] = temp temp += arr[i] # Initialize temp to 0 for sum # on right side */ temp = 0 ''' In this loop, temp variable contains sum of elements on right side excluding arr[i] */''' for i in range(n - 1, -1, -1): Sum[i] += temp temp += arr[i] for i in range(n): print(Sum[i], end = " ") # Driver Code arr = [ 3, 6, 4, 8, 9 ] n = len(arr) sumArray(arr, n) # This code is contributed by # Mohit Kumar 29
C#
// C# implementation of above approach
using System;
class Geeks {
public static void sumArray(int []arr, int n)
{
int i = 0, temp = 0;
int []Sum = new int[n];
for( i=0;i<n;i++)
Sum[i] = 0;
/* In this loop, temp variable contains
sum of elements on left side excluding
arr[i] */
for (i = 0; i < n; i++) {
Sum[i] = temp;
temp += arr[i];
}
/* Initialize temp to 0 for sum on right side */
temp = 0;
/* In this loop, temp variable contains
sum of elements on right side excluding
arr[i] */
for (i = n - 1; i >= 0; i--) {
Sum[i] += temp;
temp += arr[i];
}
for (i = 0; i < n; i++)
Console.Write(Sum[i] + " ");
}
/* Driver function to test above function*/
public static void Main()
{
int []arr = { 3, 6, 4, 8, 9 };
int n = arr.Length;
sumArray(arr, n);
}
}
// This code is contributed by inder_verma..
PHP
<?php
// PHP implementation of above approach
function sumArray($arr, $n)
{
$temp = 0;
/* Allocate memory for the sum array */
/* Initialize the sum array as 0 */
$Sum = array_fill(0, $n, 0);
/* In this loop, temp variable contains
sum of elements on left side excluding
arr[i] */
for ($i = 0; $i < $n; $i++)
{
$Sum[$i] = $temp;
$temp += $arr[$i];
}
/* Initialize temp to 0 for sum
on right side */
$temp = 0;
/* In this loop, temp variable contains
sum of elements on right side excluding
arr[i] */
for ($i = $n - 1; $i >= 0; $i--)
{
$Sum[$i] += $temp;
$temp += $arr[$i];
}
for ($i = 0; $i < $n; $i++)
echo $Sum[$i] . " ";
}
// Driver Code
$arr = array( 3, 6, 4, 8, 9 );
$n = count($arr);
sumArray($arr, $n);
// This code is contributed by
// chandan_jnu
?>
Javascript
<script>
// Javascript implementation of above approach
function sumArray(arr, n)
{
let i = 0, temp = 0;
let Sum = new Array(n);
for( i=0;i<n;i++)
Sum[i] = 0;
/* In this loop, temp variable contains
sum of elements on left side excluding
arr[i] */
for (i = 0; i < n; i++) {
Sum[i] = temp;
temp += arr[i];
}
/* Initialize temp to 0 for sum on right side */
temp = 0;
/* In this loop, temp variable contains
sum of elements on right side excluding
arr[i] */
for (i = n - 1; i >= 0; i--) {
Sum[i] += temp;
temp += arr[i];
}
for (i = 0; i < n; i++)
document.write(Sum[i] + " ");
}
let arr = [ 3, 6, 4, 8, 9 ];
let n = arr.length;
sumArray(arr, n);
// This code is contributed by decode2207.
</script>
Producción:
27 24 26 22 21
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Kirti_Mangal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA