Dada una array de n números. Necesitamos contar el número de subarreglos que tienen el producto y la suma de los elementos son iguales
Ejemplos:
Input : arr[] = {1, 3, 2}
Output : 4
The subarrays are :
[0, 0] sum = 1, product = 1,
[1, 1] sum = 3, product = 3,
[2, 2] sum = 2, product = 2 and
[0, 2] sum = 1+3+2=6, product = 1*3*2 = 6
Input : arr[] = {4, 1, 2, 1}
Output : 5
La idea es simple, verificamos para cada subarreglo si el producto y la suma de sus elementos son iguales o no. Si es así, aumente la variable del contador en 1
Implementación:
C++
// C++ program to count subarrays with
// same sum and product.
#include<bits/stdc++.h>
using namespace std;
// returns required number of subarrays
int numOfsubarrays(int arr[] , int n)
{
int count = 0; // Initialize result
// checking each subarray
for (int i=0; i<n; i++)
{
int product = arr[i];
int sum = arr[i];
for (int j=i+1; j<n; j++)
{
// checking if product is equal
// to sum or not
if (product==sum)
count++;
product *= arr[j];
sum += arr[j];
}
if (product==sum)
count++;
}
return count;
}
// driver function
int main()
{
int arr[] = {1,3,2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << numOfsubarrays(arr , n);
return 0;
}
Java
// Java program to count subarrays with
// same sum and product.
class GFG
{
// returns required number of subarrays
static int numOfsubarrays(int arr[] , int n)
{
int count = 0; // Initialize result
// checking each subarray
for (int i=0; i<n; i++)
{
int product = arr[i];
int sum = arr[i];
for (int j=i+1; j<n; j++)
{
// checking if product is equal
// to sum or not
if (product==sum)
count++;
product *= arr[j];
sum += arr[j];
}
if (product==sum)
count++;
}
return count;
}
// Driver function
public static void main(String args[])
{
int arr[] = {1,3,2};
int n = arr.length;
System.out.println(numOfsubarrays(arr , n));
}
}
Python3
# python program to # count subarrays with # same sum and product. # returns required # number of subarrays def numOfsubarrays(arr,n): count = 0 # Initialize result # checking each subarray for i in range(n): product = arr[i] sum = arr[i] for j in range(i+1,n): # checking if product is equal # to sum or not if (product==sum): count+=1 product *= arr[j] sum += arr[j] if (product==sum): count+=1 return count # Driver code arr = [1,3,2] n =len(arr) print(numOfsubarrays(arr , n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to count subarrays
// with same sum and product.
using System;
class GFG {
// returns required number
// of subarrays
static int numOfsubarrays(int []arr ,
int n)
{
// Initialize result
int count = 0;
// checking each subarray
for (int i = 0; i < n; i++)
{
int product = arr[i];
int sum = arr[i];
for (int j = i + 1; j < n; j++)
{
// checking if product is
// equal to sum or not
if (product == sum)
count++;
product *= arr[j];
sum += arr[j];
}
if (product == sum)
count++;
}
return count;
}
// Driver Code
public static void Main()
{
int []arr = {1,3,2};
int n = arr.Length;
Console.Write(numOfsubarrays(arr , n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to count subarrays
// with same sum and product.
// function returns required
// number of subarrays
function numOfsubarrays($arr , $n)
{
// Initialize result
$count = 0;
// checking each subarray
for ($i = 0; $i < $n; $i++)
{
$product = $arr[$i];
$sum = $arr[$i];
for ($j = $i + 1; $j < $n; $j++)
{
// checking if product is
// equal to sum or not
if ($product == $sum)
$count++;
$product *= $arr[$j];
$sum += $arr[$j];
}
if ($product == $sum)
$count++;
}
return $count;
}
// Driver Code
$arr = array(1, 3, 2);
$n = sizeof($arr);
echo(numOfsubarrays($arr, $n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to count subarrays
// with same sum and product.
// Returns required number
// of subarrays
function numOfsubarrays(arr, n)
{
// Initialize result
let count = 0;
// Checking each subarray
for(let i = 0; i < n; i++)
{
let product = arr[i];
let sum = arr[i];
for(let j = i + 1; j < n; j++)
{
// Checking if product is
// equal to sum or not
if (product == sum)
count++;
product *= arr[j];
sum += arr[j];
}
if (product == sum)
count++;
}
return count;
}
// Driver code
let arr = [ 1, 3, 2 ];
let n = arr.length;
document.write(numOfsubarrays(arr, n));
// This code is contributed by decode2207
</script>
Producción
4
Complejidad del tiempo : O(n 2 )
Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA