Dada una array arr[] y dos enteros L y R . La tarea es encontrar la suma del producto de todos los pares (i, j) en el rango [L, R] , tal que i ≤ j .
Entrada: arr[] = { 1, 3, 5, 8 }, L = 0, R = 2
Salida : 58
Explicación: Como 1*1 + 1*3 + 1*5 + 3*3 + 3*5 + 5 *5 = 58Entrada: arr[] = { 2, 1, 4, 5, 3, 2, 1 }, L = 1, R = 5
Salida: 140
Enfoque ingenuo: el enfoque de fuerza bruta se puede implementar directamente multiplicando los índices usando dos bucles anidados y almacenando la suma en una variable.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum
// of (arr[i]*arr[j]) for all i and j
// between the index L and R
int sum_of_products(int arr[], int N, int L,
int R)
{
int sum = 0;
for (int i = L; i <= R; i++) {
for (int j = i; j <= R; j++) {
sum += arr[i] * arr[j];
}
}
return sum;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 0;
int R = 2;
cout << sum_of_products(arr, N, L, R);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
public class GFG {
// Function to return the sum
// of (arr[i]*arr[j]) for all i and j
// between the index L and R
static int sum_of_products(int[] arr, int N, int L,
int R)
{
int sum = 0;
for (int i = L; i <= R; i++) {
for (int j = i; j <= R; j++) {
sum += arr[i] * arr[j];
}
}
return sum;
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, 3, 5, 8 };
int N = arr.length;
int L = 0;
int R = 2;
System.out.println(sum_of_products(arr, N, L, R));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach: ## Function to return the sum ## of (arr[i]*arr[j]) for all i and j ## between the index L and R def sum_of_products(arr, N, L, R): sum1 = 0 for i in range(L, R + 1): for j in range(i, R + 1): sum1 += arr[i] * arr[j] return sum1 ## Driver code if __name__ == "__main__": arr = [ 1, 3, 5, 8 ] N = len(arr) L = 0 R = 2 print(sum_of_products(arr, N, L, R)) # This code is contributed by entertain2022.
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to return the sum
// of (arr[i]*arr[j]) for all i and j
// between the index L and R
static int sum_of_products(int[] arr, int N, int L,
int R)
{
int sum = 0;
for (int i = L; i <= R; i++) {
for (int j = i; j <= R; j++) {
sum += arr[i] * arr[j];
}
}
return sum;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 3, 5, 8 };
int N = arr.Length;
int L = 0;
int R = 2;
Console.WriteLine(sum_of_products(arr, N, L, R));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to return the sum
// of (arr[i]*arr[j]) for all i and j
// between the index L and R
function sum_of_products(arr, N, L, R) {
let sum = 0;
for (let i = L; i <= R; i++) {
for (let j = i; j <= R; j++) {
sum += arr[i] * arr[j];
}
}
return sum;
}
// Driver code
let arr = [1, 3, 5, 8];
let N = arr.length
let L = 0;
let R = 2;
document.write(sum_of_products(arr, N, L, R));
// This code is contributed by Potta Lokesh
</script>
Producción
58
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver de manera eficiente utilizando la técnica de suma de prefijos. En este método, almacene la suma del prefijo en el cálculo previo y luego itere un solo ciclo de L a R y multiplique la suma del prefijo correspondiente de ese índice al último índice.
Básicamente , 1*1+1*3+1*5+3*3+3*5+5*5 se puede escribir como 1*(1+3+5)+3*(3+5)+5*(5 ) = 1*(prefix_sum de 1 a 5)+3*(prefix_sum de 3 a 5)+5*(prefix_sum de 5 a 5)
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the sum of
// (arr[i]*arr[j]) for all i and j
// between the index L and R
int sum_of_products(int arr[], int n, int L,
int R)
{
int sum = 0;
// Pre-calculating Prefix sum
int prefix_sum[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i];
}
// Using prefix sum to find
// summation of products
for (int i = L; i <= R; i++) {
// if-else for i==0 case
// in prefix sum
if (i != 0)
sum += arr[i]
* (prefix_sum[R]
- prefix_sum[i - 1]);
else
sum += arr[i] * (prefix_sum[R]);
}
return sum;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 5, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 0;
int R = 2;
cout << sum_of_products(arr, N, L, R);
return 0;
}
Java
// Java code to implement above approach
import java.util.*;
class GFG{
// Function to return the sum of
// (arr[i]*arr[j]) for all i and j
// between the index L and R
static int sum_of_products(int arr[], int n, int L,
int R)
{
int sum = 0;
// Pre-calculating Prefix sum
int []prefix_sum = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i];
}
// Using prefix sum to find
// summation of products
for (int i = L; i <= R; i++) {
// if-else for i==0 case
// in prefix sum
if (i != 0)
sum += arr[i]
* (prefix_sum[R]
- prefix_sum[i - 1]);
else
sum += arr[i] * (prefix_sum[R]);
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 5, 8 };
int N = arr.length;
int L = 0;
int R = 2;
System.out.print(sum_of_products(arr, N, L, R));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach: ## Function to return the sum of ## (arr[i]*arr[j]) for all i and j ## between the index L and R def sum_of_products(arr, n, L, R): sum = 0 ## Pre-calculating Prefix sum prefix_sum = [0]*n; prefix_sum[0] = arr[0]; for i in range(1, n): prefix_sum[i] = prefix_sum[i - 1] + arr[i] ## Using prefix sum to find ## summation of products for i in range(L, R + 1): ## if-else for i==0 case ## in prefix sum if (i != 0): sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]) else: sum += arr[i] * (prefix_sum[R]) return sum ## Driver code if __name__=='__main__': arr = [1, 3, 5, 8] N = len(arr) L = 0 R = 2 print(sum_of_products(arr, N, L, R)) # This code is contributed by subhamgoyal2014.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the sum of
// (arr[i]*arr[j]) for all i and j
// between the index L and R
static int sum_of_products(int[] arr, int n, int L,
int R)
{
int sum = 0;
// Pre-calculating Prefix sum
int []prefix_sum = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i];
}
// Using prefix sum to find
// summation of products
for (int i = L; i <= R; i++) {
// if-else for i==0 case
// in prefix sum
if (i != 0)
sum += arr[i]
* (prefix_sum[R]
- prefix_sum[i - 1]);
else
sum += arr[i] * (prefix_sum[R]);
}
return sum;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 5, 8 };
int N = arr.Length;
int L = 0;
int R = 2;
Console.Write(sum_of_products(arr, N, L, R));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript code to implement above approach
// Function to return the sum of
// (arr[i]*arr[j]) for all i and j
// between the index L and R
function sum_of_products(arr , n , L , R) {
var sum = 0;
// Pre-calculating Prefix sum
var prefix_sum = Array(n).fill(0);
prefix_sum[0] = arr[0];
for (i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
}
// Using prefix sum to find
// summation of products
for (i = L; i <= R; i++) {
// if-else for i==0 case
// in prefix sum
if (i != 0)
sum += arr[i] * (prefix_sum[R] - prefix_sum[i - 1]);
else
sum += arr[i] * (prefix_sum[R]);
}
return sum;
}
// Driver code
var arr = [ 1, 3, 5, 8 ];
var N = arr.length;
var L = 0;
var R = 2;
document.write(sum_of_products(arr, N, L, R));
// This code is contributed by umadevi9616
</script>
Producción
58
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pushpeshrajdx01 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA