Given a array of n numbers. We need to count the number of subarrays having the product and sum of elements are equal
Examples:
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
The idea is simple, we check for each subarray that if product and sum of its elements are equal or not. If it is then increase the counter variable by 1
Implementation:
C++
// C++ program to count subarrays with// same sum and product.#include<bits/stdc++.h>using namespace std;// returns required number of subarraysint 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 functionint 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 subarraysdef 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 codearr = [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 subarraysfunction 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 subarraysfunction 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 codelet arr = [ 1, 3, 2 ];let n = arr.length;document.write(numOfsubarrays(arr, n));// This code is contributed by decode2207</script> |
Output
4
Time Complexity : O(n2)
This article is contributed by Ayush Jha. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
