PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Soumyadeep Pal
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh
DIFFICULTY:
Simple
PREREQUISITES:
Sorting or usage of map/dictionary
PROBLEM:
Given an array A of length N, delete the minimum number of elements from it such that among the remaining elements, all pairwise differences are equal.
QUICK EXPLANATION:
If more than 2 elements remain, they must all be equal. So, the answer is either 0 (if N = 1), N-2, or N - M where M is the maximum frequency of some element of A.
EXPLANATION:
First, note that any array of size \leq 2 trivially satisfies the condition, so there is no need to delete anything from it.
Now, suppose N \geq 3.
The above observation tells us that the answer will never be more than N-2, because we can simply delete any N-2 elements from the array and the remaining two elements will satisfy the condition.
What happens if the answer is less than N-2?
That would mean that at least 3 elements remain - say these are a, b, c with a\leq b\leq c.
The condition on pairwise differences tells us that c-b = c-a = b-a
This, of course, is only possible when a = b = c.
So, if the answer is less than N-2, all remaining elements must be equal.
This fact leads us to a simple solution - count the frequency of each element of A, and let M be the maximum of these frequencies. The answer is then \min(N-2, N-M).
How to count the frequency of every element fast?
Note that the elements of the array can be as large as 10^9, so creating a frequency array and updating the count of each element will not work, it would need too much memory.
Instead, do the same thing but using a map or unordered_map (C++) / TreeMap or HashMap (Java) / dictionary (python) to keep the memory usage down to \mathcal{O}(N)
There are other ways to do this as well without needing to resort to any data structures:
Sort the array. Now, all equal elements will form a continuous subarray, and the lengths of these subarrays can be found with binary search / two pointers.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase, depending on implementation.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve(int tc) {
int n; cin >> n;
map<int, int> m;
for (int i = 0; i < n; i++) {
int x; cin >> x;
m[x]++;
}
int ans = n, cnt = 0;
for (auto u : m) {
ans = min(ans, n - u.second);
cnt++;
}
if (cnt >= 2) {
ans = min(ans, n - 2);
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}
Tester's Solution
//By TheOneYouWant
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin >> tests;
while(tests--){
int n;
cin >> n;
map<int,int> m;
for(int i = 0; i < n; i++){
int x;
cin >> x;
m[x]++;
}
if(n == 1){
cout << 0 << endl;
continue;
}
int ans = n-2;
for(map<int,int>::iterator it = m.begin(); it != m.end(); it++){
ans = min(ans, n - (*it).second);
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
import sys, collections
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n <= 2:
print(0)
continue
freq = collections.Counter(a)
ans = n-max(2, max(freq.values()))
print(ans)