Solution Based on PigeonHole Sorting Concept


#1

Recursed into the solution using the Pigeonhole Concept.

  1. Divided the segment in 3 parts from min-ele - max_ele.

  2. count the number of all the segments whichever has more than n/3, considered those intervals again.
    (It’s a sure shot that at least one segment would get deleted.

  3. repeated above two steps for the next items in the queue.

    struct bucket { int max_ele = INT_MIN, min_ele = INT_MAX, count = 0; }; int Solution::repeatedNumber(const vector<int> &A) { int n = A.size(); int minele = 1.0*(*min_element(A.begin(), A.end())); int maxele = 1.0*(*max_element(A.begin(), A.end())); if(maxele == minele) return maxele; bucket original; original.max_ele = maxele, original.min_ele = minele, original.count = n; queue<bucket> q; q.push(original); while(!q.empty()) { bucket top = q.front(); q.pop(); float delta = (1.0*(top.max_ele - top.min_ele))/3.0; bucket dividend[3]; int mx = 0; // cout << top.max_ele << ' ' << top.min_ele << ' ' << delta << endl; for(int i = 0; i < n; i++) { if(A[i] < top.min_ele || A[i] > top.max_ele) continue; if(A[i] == top.max_ele) { mx++; continue; } int index = (1.0*(A[i] - top.min_ele))/delta; dividend[index].count++; dividend[index].max_ele = max(dividend[index].max_ele, A[i]); dividend[index].min_ele = min(dividend[index].min_ele, A[i]); } if(mx > n/3) return top.max_ele; for(int i = 0; i < 3; i++) { if(dividend[i].count > n/3) { if(dividend[i].max_ele == dividend[i].min_ele) return dividend[i].max_ele; q.push(dividend[i]); } } } return -1; }Preformatted text


#2
int Solution::repeatedNumber(const vector<int> &A) {
 struct bucket{int max_ele = INT_MIN, min_ele = INT_MAX, count = 0;};
 int n = A.size();
 int minele = 1.0*(*min_element(A.begin(), A.end()));
 int maxele = 1.0*(*max_element(A.begin(), A.end()));
 if(maxele == minele) return maxele;
 bucket original;
 original.max_ele = maxele, original.min_ele = minele, original.count = n;
 queue<bucket> q;
 q.push(original);
 while(!q.empty()) { 
 bucket top = q.front();
 q.pop();
 float delta = (1.0*(top.max_ele - top.min_ele))/3.0;
 bucket dividend[3];
 int mx = 0; 
 // cout << top.max_ele << ' ' << top.min_ele << ' ' << delta << endl;
 for(int i = 0; i < n; i++) {
	 if(A[i] < top.min_ele || A[i] > top.max_ele) continue;
	 if(A[i] == top.max_ele) { 
		 mx++;
		 continue; 
		} 
	 int index = (1.0*(A[i] - top.min_ele))/delta;
	 dividend[index].count++;
	 dividend[index].max_ele = max(dividend[index].max_ele, A[i]);
	 dividend[index].min_ele = min(dividend[index].min_ele, A[i]);
	} 
	 if(mx > n/3) return top.max_ele;
	 for(int i = 0; i < 3; i++) {
		 if(dividend[i].count > n/3) {
			 if(dividend[i].max_ele == dividend[i].min_ele) return dividend[i].max_ele;
			 q.push(dividend[i]); } 
		} 
	} return -1; 
}