算法：如何计算乘积和总和相等的子数组的个数？

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定n个数字的数组。我们需要计算具有乘积和元素总和相等的子数组的数量

例子：

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

这个想法很简单, 我们检查每个子数组是否乘积和其元素的总和是否相等。如果是, 则将计数器变量加1

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.
?>

输出如下：

4

时间复杂度：O(n^2)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。