N/3 Repeat Number

• Time : $O(n)$
• Space : $O(1)$

unordered_set<int> dnc(const vector<int>& A, int l, int r) {
    unordered_map<int, int> freq;
    int ma = 0;
    unordered_set<int> res;
    for(int i = l; i < r; i++) ++freq[A[i]];
    
    for(auto [k,v] : freq) if(v >= (r-l)/3.) res.insert(k);
    return res;
}

int Solution::repeatedNumber(const vector<int> &A) {
    int n3 = floor(1. * A.size() / 3);
    auto cand1 = dnc(A,0,n3);
    auto cand2 = dnc(A,n3,2*n3);
    auto cand3 = dnc(A,2*n3,A.size());
    
    unordered_map<int, int> freq;
    int ma = 0;
    for(int i = 0; i < A.size(); i++) {
        if(cand1.count(A[i]) or cand2.count(A[i]) or cand3.count(A[i])) {
            if(++freq[A[i]] > freq[ma]) ma = A[i];
        }
    }
    return freq[ma] > n3 ? ma : -1;
}