Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar la suma de todos los elementos de todos los posibles subarreglos de longitud impar.
Ejemplos:
Entrada: arr[] = {3, 2, 4}
Salida: 18
Explicación:
Los subarreglos de longitud impar junto con su suma son los siguientes:
1) {3} = la suma es 3.
2) {2} = la suma es 2.
3) {4} = la suma es 4.
4) {3, 2, 4} = la suma es 3 + 2 + 4 = 9.
Por lo tanto, la suma de todos los subarreglos = 3 + 2 + 4 + 9 = 18.Entrada: arr[] = {1, 2, 1, 2}
Salida: 15
Explicación:
Los subarreglos de longitud impar junto con su suma son los siguientes:
1) {1} = la suma es 1.
2) {2} = la suma es 2.
3) {1} = la suma es 1.
4) {2} = la suma es 2.
5) {1, 2, 1} = la suma es 1 + 2 + 1 = 4.
6) {2, 1, 2 } = la suma es 2 + 1 + 2 = 5.
Por lo tanto, la suma de todos los subarreglos = 1 + 2 + 1 + 2 + 4 + 5 = 15.
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de longitud impar a partir del arreglo dado y encontrar la suma de todos esos subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum
// of all odd length subarrays
int OddLengthSum(vector<int>& arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.size();
// Traverse the array
for (int i = 0; i < l; i++) {
// Generate all subarray of
// odd length
for (int j = i; j < l; j += 2) {
for (int k = i; k <= j; k++) {
// Add the element to sum
sum += arr[k];
}
}
}
// Return the final sum
return sum;
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 1, 5, 3, 1, 2 };
// Function Call
cout << OddLengthSum(arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to calculate the sum
// of all odd length subarrays
static int OddLengthSum(int[] arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.length;
// Traverse the array
for(int i = 0; i < l; i++)
{
// Generate all subarray of
// odd length
for(int j = i; j < l; j += 2)
{
for(int k = i; k <= j; k++)
{
// Add the element to sum
sum += arr[k];
}
}
}
// Return the final sum
return sum;
}
// Driver Code
public static void main (String[] args)
{
// Given array arr[]
int[] arr = { 1, 5, 3, 1, 2 };
// Function call
System.out.print(OddLengthSum(arr));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to calculate the sum # of all odd length subarrays def OddLengthSum(arr): # Stores the sum sum = 0 # Size of array l = len(arr) # Traverse the array for i in range(l): # Generate all subarray of # odd length for j in range(i, l, 2): for k in range(i, j + 1, 1): # Add the element to sum sum += arr[k] # Return the final sum return sum # Driver Code # Given array arr[] arr = [ 1, 5, 3, 1, 2 ] # Function call print(OddLengthSum(arr)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate the sum
// of all odd length subarrays
static int OddLengthSum(int[] arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.Length;
// Traverse the array
for(int i = 0; i < l; i++)
{
// Generate all subarray of
// odd length
for(int j = i; j < l; j += 2)
{
for(int k = i; k <= j; k++)
{
// Add the element to sum
sum += arr[k];
}
}
}
// Return the final sum
return sum;
}
// Driver Code
public static void Main ()
{
// Given array arr[]
int[] arr = { 1, 5, 3, 1, 2 };
// Function call
Console.Write(OddLengthSum(arr));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// javascript program for the above approach
// Function to calculate the sum
// of all odd length subarrays
function OddLengthSum(arr)
{
// Stores the sum
var sum = 0;
// Size of array
var l = arr.length;
// Traverse the array
for(var i = 0; i < l; i++)
{
// Generate all subarray of
// odd length
for(var j = i; j < l; j += 2)
{
for(var k = i; k <= j; k++)
{
// Add the element to sum
sum += arr[k];
}
}
}
// Return the final sum
return sum;
}
// Driver Code
// Given array arr[]
var arr = [ 1, 5, 3, 1, 2 ]
// Function call
document.write(OddLengthSum(arr));
// This code is contributed by bunnyram19.
</script>
48
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar el siguiente patrón después de generar todos los subarreglos de longitud impar:
- Para cualquier elemento en el índice idx hay (idx + 1) opciones en el lado izquierdo y (N – idx) opciones en el lado derecho.
- Por lo tanto, para cualquier elemento arr[i] , la cuenta de arr[i] es (i + 1) * (N – i) en todos los subarreglos.
- Entonces, para un elemento arr[i] , hay ((i + 1) * (N – i) + 1) / 2 subarreglos con longitud impar.
- Finalmente, arr[i] tendrá un total de ((i + 1) * (n – i) + 1) / 2 frecuencias en la suma.
Por lo tanto, para encontrar la suma de todos los elementos de todos los subarreglos de longitud impar, la idea es iterar sobre el arreglo y para cada i -ésimo elemento del arreglo, agregar [ ((i + 1) * (n – i) + 1) / 2]*arr[i] a la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the sum of all
// the element of subarrays of odd length
int OddLengthSum(vector<int>& arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.size();
// Traverse the given array arr[]
for (int i = 0; i < l; i++) {
// Add to the sum for each
// contribution of the arr[i]
sum += (((i + 1)
* (l - i)
+ 1)
/ 2)
* arr[i];
}
// Return the final sum
return sum;
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 1, 5, 3, 1, 2 };
// Function Call
cout << OddLengthSum(arr);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function that finds the sum of all
// the element of subarrays of odd length
static int OddLengthSum(int []arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.length;
// Traverse the given array arr[]
for(int i = 0; i < l; i++)
{
// Add to the sum for each
// contribution of the arr[i]
sum += (((i + 1) * (l - i) +
1) / 2) * arr[i];
}
// Return the final sum
return sum;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int []arr = { 1, 5, 3, 1, 2 };
// Function call
System.out.print(OddLengthSum(arr));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function that finds the sum of all # the element of subarrays of odd length def OddLengthSum(arr): # Stores the sum Sum = 0 # Size of array l = len(arr) # Traverse the given array arr[] for i in range(l): # Add to the sum for each # contribution of the arr[i] Sum += ((((i + 1) * (l - i) + 1) // 2) * arr[i]) # Return the final sum return Sum # Driver code # Given array arr[] arr = [ 1, 5, 3, 1, 2 ] # Function call print(OddLengthSum(arr)) # This code is contributed by divyeshrabadiya07
C#
// C# program for
// the above approach
using System;
class GFG{
// Function that finds the
// sum of all the element of
// subarrays of odd length
static int OddLengthSum(int []arr)
{
// Stores the sum
int sum = 0;
// Size of array
int l = arr.Length;
// Traverse the given array []arr
for(int i = 0; i < l; i++)
{
// Add to the sum for each
// contribution of the arr[i]
sum += (((i + 1) *
(l - i) + 1) / 2) * arr[i];
}
// Return the readonly sum
return sum;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 5, 3, 1, 2};
// Function call
Console.Write(OddLengthSum(arr));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function that finds the sum of all
// the element of subarrays of odd length
function OddLengthSum(arr)
{
// Stores the sum
let sum = 0;
// Size of array
let l = arr.length;
// Traverse the given array arr[]
for(let i = 0; i < l; i++)
{
// Add to the sum for each
// contribution of the arr[i]
sum += Math.floor(((i + 1) * (l - i) +
1) / 2) * arr[i];
}
// Return the final sum
return sum;
}
// Driver Code
// Given array arr[]
let arr = [ 1, 5, 3, 1, 2 ];
// Function call
document.write(OddLengthSum(arr));
// This code is contributed by target_2.
</script>
48
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por whysodarkbro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA