fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. pair<int, int> findFastestZeroSumSubarrayElement(const vector<int>& arr) {
  8.     unordered_map<int, int> prefixSumMap; // Tracks first occurrence of prefix sums
  9.     unordered_map<int, int> globalFreq;  // Efficient frequency tracking
  10.     int prefixSum = 0, maxFreq = 0, mostRepeatedElement = arr[0];
  11.  
  12.     prefixSumMap[0] = -1; // Handles cases where subarray starts from 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.             for (int j = prefixSumMap[prefixSum] + 1; j <= i; j++) {
  19.                 int num = arr[j];
  20.                 globalFreq[num]++;
  21.                 if (globalFreq[num] > maxFreq) {
  22.                     maxFreq = globalFreq[num];
  23.                     mostRepeatedElement = num;
  24.                 }
  25.             }
  26.         } else {
  27.             prefixSumMap[prefixSum] = i; // First occurrence of prefixSum
  28.         }
  29.     }
  30.  
  31.     return {mostRepeatedElement, maxFreq};
  32. }
  33.  
  34. int main() {
  35.     vector<int> arr = {1, 1, -1, 0, 0, 1, 0, -1, -1, -1, 0, 1, 0, 0, 1, 1, 0, 0, -1, -1};
  36.  
  37.     auto [mostRepeatedElement, mostRepeatedCount] = findFastestZeroSumSubarrayElement(arr);
  38.  
  39.     cout << "Most Repeated Element in Zero-Sum Subarray: " << mostRepeatedElement 
  40.          << " (Repeated " << mostRepeatedCount << " times)" << endl;
  41.  
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Most Repeated Element in Zero-Sum Subarray: 0 (Repeated 73 times)
https://ideone.com/KPxCtC
language:
C++ (gcc 8.3)
created:
12 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!