fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. pair<vector<long long >,long long > solve(vector<long long >& arr) {
  9.     unordered_map<long long , long long > mapaPrefiksnihSuma; 
  10.     unordered_map<long long , long long > frequencyMap; 
  11.     long long  maxUcestalost = 0, najucestalijiElement = arr[0];
  12.     long long  start = -1, end = -1;
  13.     long long  prefiksnaSuma = 0;
  14.  
  15.     mapaPrefiksnihSuma[0] = -1; 
  16.  
  17.     for (long long  i = 0; i < arr.size(); i++) {
  18.         prefiksnaSuma += arr[i];
  19.  
  20.         if (mapaPrefiksnihSuma.find(prefiksnaSuma) != mapaPrefiksnihSuma.end()) {
  21.             long long leftIndex = mapaPrefiksnihSuma[prefiksnaSuma] + 1;
  22.             vector<long long> subarray(arr.begin() + leftIndex, arr.begin() + i + 1);
  23.  
  24.  
  25.             unordered_map<long long, long long> tempFreq;
  26.             for (long long num : subarray) tempFreq[num]++;
  27.  
  28.  
  29.             for (auto& [num, freq] : tempFreq) {
  30.                 if (freq > maxUcestalost) {
  31.                     maxUcestalost = freq;
  32.                     najucestalijiElement = num;
  33.                     start = leftIndex;
  34.                     end = i;
  35.                 }
  36.             }
  37.         } else {
  38.             mapaPrefiksnihSuma[prefiksnaSuma] = i;
  39.         }
  40.     }
  41.  
  42.     vector<long long> bestSubarray;
  43.     if (start != -1) {
  44.         bestSubarray.assign(arr.begin() + start, arr.begin() + end + 1);
  45.     }
  46.  
  47.     return {bestSubarray, najucestalijiElement};
  48. }
  49.  
  50. int main() {
  51.     vector<long long> niz;
  52.     long long n;
  53.     cin >> n;
  54.     for (long long i = 0; i < n; i++){
  55.     	long long temp;
  56.     	cin >> temp;
  57.     	niz.push_back(temp);
  58.     }
  59.  
  60.     auto [subarray, mostFrequent] = solve(niz);
  61.  
  62.     long long brojac = 0;
  63.  
  64.     for (long long num : subarray) 
  65.     	if(num == mostFrequent) 
  66.     		brojac++;
  67.     cout << brojac;
  68.     cout << "\nMost Repeated Element: " << mostFrequent << endl;
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5328KB
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 
8
Most Repeated Element: 0
https://ideone.com/98qcj2
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!