fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. pair<vector<int>, pair<int, int>> findZeroSumSubarrayWithMostRepeatedElement(vector<int>& arr) {
  8.     unordered_map<int, int> prefixSumMap; // Stores prefix sums and their first occurrence index
  9.     int prefixSum = 0;
  10.     int start = -1, end = -1;
  11.     int maxFreq = 0, mostRepeatedElement = arr[0], mostRepeatedCount = 0;
  12.  
  13.     prefixSumMap[0] = -1; // Handles cases where subarray starts at index 0
  14.  
  15.     for (int i = 0; i < arr.size(); i++) {
  16.         prefixSum += arr[i];
  17.  
  18.         if (prefixSumMap.find(prefixSum) != prefixSumMap.end()) {
  19.             int leftIndex = prefixSumMap[prefixSum] + 1;
  20.             vector<int> subarray(arr.begin() + leftIndex, arr.begin() + i + 1);
  21.  
  22.             // Count element frequencies in this subarray
  23.             unordered_map<int, int> tempFreq;
  24.             for (int num : subarray) tempFreq[num]++;
  25.  
  26.             // Find the most frequent element
  27.             for (auto& [num, freq] : tempFreq) {
  28.                 if (freq > maxFreq) {
  29.                     maxFreq = freq;
  30.                     mostRepeatedElement = num;
  31.                     mostRepeatedCount = freq;
  32.                     start = leftIndex;
  33.                     end = i;
  34.                 }
  35.             }
  36.         } else {
  37.             prefixSumMap[prefixSum] = i;
  38.         }
  39.     }
  40.  
  41.     vector<int> bestSubarray;
  42.     if (start != -1) {
  43.         bestSubarray.assign(arr.begin() + start, arr.begin() + end + 1);
  44.     }
  45.  
  46.     return {bestSubarray, {mostRepeatedElement, mostRepeatedCount}};
  47. }
  48.  
  49. int main() {
  50.     vector<int> arr = {4, 2, -3, 1, 6, -3, 1, 3, -2, -1, 4, -4, 2};
  51.  
  52.     auto [subarray, elementInfo] = findZeroSumSubarrayWithMostRepeatedElement(arr);
  53.     int mostRepeatedElement = elementInfo.first;
  54.     int mostRepeatedCount = elementInfo.second;
  55.  
  56.     cout << "Optimal Zero-Sum Subarray: ";
  57.     for (int num : subarray) cout << num << " ";
  58.     cout << "\nMost Repeated Element: " << mostRepeatedElement 
  59.          << " (Repeated " << mostRepeatedCount << " times)" << endl;
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
20
1 1 -1 0 0 1 0 -1 -1 -1 0 1 0 0 1 1 0 0 -1 -1
stdout
copy 
Optimal Zero-Sum Subarray: 2 -3 1 
Most Repeated Element: 1 (Repeated 1 times)
https://ideone.com/JZLAtY
language:
C++14 (gcc 8.3)
created:
8 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!