Given an array arr[], the task is to count elements in an array such that there exists a subarray whose sum is equal to this element.
Note: Length of subarray must be greater than 1.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 4
Explanation:
There are 4 such elements in array –
arr[2] = 3 => arr[0-1] => 1 + 2 = 3
arr[4] = 5 => arr[1-2] => 2 + 3 = 5
arr[5] = 6 => arr[0-2] => 1 + 2 + 3 = 6
arr[6] = 7 => arr[2-3] => 3 + 4 = 7
Input: arr[] = {1, 2, 3, 3}
Output: 2
There are 2 such elements in array –
arr[2] = 3 => arr[0-1] => 1 + 2 = 3
arr[3] = 3 => arr[0-1] => 1 + 2 = 3
Approach: The idea is to store the frequency of the elements of the array in a hash-map. Then, iterate over every possible subarray and check that its sum is present in the hash-map. If yes, then increment the count of such elements by their frequency.
Algorithm:
- Start the function countElement with the given array ‘arr’ and its length ‘n’.
- Create a map named ‘freq’ to store the frequency of each element in the array.
- Initialize a variable named ‘ans’ to 0.
- Loop through the array ‘arr’ and increment the frequency of each element in the ‘freq’ map.
- Loop through the array again, starting from the first index and going up to the second last index.
- Within the previous loop, initialize a variable named ‘tmpsum’ to the value of the current array element.
- Loop through the array again, starting from the next index and going up to the last index.
- Within the previous loop, add the current array element to ‘tmpsum’.
- Check if ‘tmpsum’ exists as a key in the ‘freq’ map. If it does, increment ‘ans’ by the value corresponding to that key.
- Return the value of ‘ans’.
- End.
Pseudocode:
countElement(arr, n):
freq = create a new empty map
ans = 0
for i from 0 to n-1:
freq[arr[i]] += 1
for i from 0 to n-2:
tmpsum = arr[i]
for j from i+1 to n-1:
tmpsum += arr[j]
if tmpsum is a key in freq:
ans += freq[tmpsum]
return ans
main:
arr = create a new integer array with some values
n = calculate the size of arr
result = countElement(arr, n)
print result
Below is the implementation of the above approach:
C++
// C++ implementation to count the// elements such that their exist// a subarray whose sum is equal to// this element#include <bits/stdc++.h>using namespace std;// Function to count the elements// such that their exist a subarray// whose sum is equal to this elementint countElement(int arr[], int n){ map<int, int> freq; int ans = 0; // Loop to count the frequency for (int i = 0; i < n; i++) { freq[arr[i]]++; } // Loop to iterate over every possible // subarray of the array for (int i = 0; i < n - 1; i++) { int tmpsum = arr[i]; for (int j = i + 1; j < n; j++) { tmpsum += arr[j]; if (freq.find(tmpsum) != freq.end()) { ans += freq[tmpsum]; } } } return ans;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countElement(arr, n) << endl; return 0;} |
Java
// Java implementation to count the // elements such that their exist // a subarray whose sum is equal to // this element import java.util.*;class GFG {// Function to count the elements // such that their exist a subarray // whose sum is equal to this elementstatic int countElement(int arr[], int n){ int freq[] = new int[n + 1]; int ans = 0; // Loop to count the frequency for(int i = 0; i < n; i++) { freq[arr[i]]++; } // Loop to iterate over every possible // subarray of the array for(int i = 0; i < n - 1; i++) { int tmpsum = arr[i]; for(int j = i + 1; j < n; j++) { tmpsum += arr[j]; if (tmpsum <= n) { ans += freq[tmpsum]; freq[tmpsum] = 0; } } } return ans;}// Driver Codepublic static void main(String args[]){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.length; System.out.println(countElement(arr, n));}}// This code is contributed by rutvik_56 |
Python3
# Python3 implementation to count the# elements such that their exist# a subarray whose sum is equal to # this element# Function to count element such # that their exist a subarray whose# sum is equal to this elementdef countElement(arr, n): freq = {} ans = 0 # Loop to compute frequency # of the given elements for i in range(n): freq[arr[i]] = \ freq.get(arr[i], 0) + 1 # Loop to iterate over every # possible subarray of array for i in range(n-1): tmpsum = arr[i] for j in range(i + 1, n): tmpsum += arr[j] if tmpsum in freq: ans += freq[tmpsum] return ans # Driver Codeif __name__ == "__main__": arr =[1, 2, 3, 4, 5, 6, 7] n = len(arr) print(countElement(arr, n)) |
C#
// C# implementation to count the // elements such that their exist // a subarray whose sum is equal to // this element using System;class GFG {// Function to count the elements // such that their exist a subarray // whose sum is equal to this elementstatic int countElement(int[] arr, int n){ int[] freq = new int[n + 1]; int ans = 0; // Loop to count the frequency for(int i = 0; i < n; i++) { freq[arr[i]]++; } // Loop to iterate over every possible // subarray of the array for(int i = 0; i < n - 1; i++) { int tmpsum = arr[i]; for(int j = i + 1; j < n; j++) { tmpsum += arr[j]; if (tmpsum <= n) { ans += freq[tmpsum]; freq[tmpsum] = 0; } } } return ans;}// Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.Length; Console.WriteLine(countElement(arr, n));}}// This code is contributed by AbhiThakur |
Javascript
<script>// Javascript implementation to count the // elements such that their exist // a subarray whose sum is equal to // this element // Function to count the elements // such that their exist a subarray // whose sum is equal to this elementfunction countElement(arr, n){ let freq = Array.from({length: n+1}, (_, i) => 0); let ans = 0; // Loop to count the frequency for(let i = 0; i < n; i++) { freq[arr[i]]++; } // Loop to iterate over every possible // subarray of the array for(let i = 0; i < n - 1; i++) { let tmpsum = arr[i]; for(let j = i + 1; j < n; j++) { tmpsum += arr[j]; if (tmpsum <= n) { ans += freq[tmpsum]; freq[tmpsum] = 0; } } } return ans;}// Driver Code let arr = [ 1, 2, 3, 4, 5, 6, 7 ]; let n = arr.length; document.write(countElement(arr, n)); </script> |
Output:
4
Time Complexity: O(N2)
Space Complexity: O(N)
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!
