fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. pair<int, int> findZeroSumSubarrayWithMostRepeatedElement(const vector<int>& arr) {
  8.     unordered_map<int, int> prefixSumMap; // Maps prefix sum to index
  9.     unordered_map<int, int> globalFreq;  // Tracks global element frequency
  10.     int prefixSum = 0, maxFreq = 0, mostRepeatedElement = arr[0];
  11.  
  12.     prefixSumMap[0] = -1; // Handles cases where subarray starts at index 0
  13.  
  14.     for (int i = 0; i < arr.size(); i++) {
  15.         prefixSum += arr[i];
  16.  
  17.         if (prefixSumMap.find(prefixSum) != prefixSumMap.end()) {
  18.             int startIdx = prefixSumMap[prefixSum] + 1;
  19.  
  20.             // Update frequency for the elements in the new valid subarray
  21.             for (int j = startIdx; j <= i; j++) {
  22.                 globalFreq[arr[j]]++;
  23.                 if (globalFreq[arr[j]] > maxFreq) {
  24.                     maxFreq = globalFreq[arr[j]];
  25.                     mostRepeatedElement = arr[j];
  26.                 }
  27.             }
  28.         } else {
  29.             prefixSumMap[prefixSum] = i;
  30.         }
  31.     }
  32.  
  33.     return {mostRepeatedElement, maxFreq};
  34. }
  35.  
  36. int main() {
  37.     vector<int> arr = {1, 1, -1, 0, 0, 1, 0, -1, -1, -1, 0, 1, 0, 0, 1, 1, 0, 0, -1, -1};
  38.  
  39.     auto [mostRepeatedElement, mostRepeatedCount] = findZeroSumSubarrayWithMostRepeatedElement(arr);
  40.  
  41.     cout << "Most Repeated Element in Zero-Sum Subarray: " << mostRepeatedElement 
  42.          << " (Repeated " << mostRepeatedCount << " times)" << endl;
  43.  
  44.     return 0;
  45. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Most Repeated Element in Zero-Sum Subarray: 0 (Repeated 73 times)
https://ideone.com/c7D8yu
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!