积与和相等的子阵列数-yiteyi-C++库

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

null

例如：

Input  : arr[] = {1, 3, 2}Output : 4The 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 = 6Input : 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.                       
                         ?>                       

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>                       

输出：

时间复杂度：O（n） ^2. )

本文由 阿尤什·贾哈 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章