n/3 number appears in array elements
// CPP program to find if any element appears // more than n/3. #include <bits/stdc++.h> using namespace std; int appearsNBy3(int arr[], int n) { int count1 = 0, count2 = 0; int first=INT_MAX , second=INT_MAX ; for (int i = 0; i < n; i++) { // if this element is previously seen, // increment count1. if (first == arr[i]) count1++; // if this element is previously seen, // increment count2. else if (second == arr[i]) count2++; else if (count1 == 0) { count1++; first = arr[i]; } else if (count2 == 0) { count2++; second = arr[i]; } // if current element is different from // both the previously seen variables, // decrement both the counts. else { count1--; count2--; } } count1 = 0; count2 = 0; // Again traverse the array and find the // actual counts. for (int i = 0; i < n; i++) { if (arr[i] == first) count1++; else if (arr[i] == second) count2++; } if (count1 > n / 3) return first; if (count2 > n / 3) return second; return -1; } int main() { int arr[] = { 1, 2, 3, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << appearsNBy3(arr, n) << endl; return 0; }
