EQDIFFER - Editorial

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)
4 Likes

i thought if the numbers are consecutive then differences in the pairs will be same.

E.g : 1 2 3 4 6 7

here difference between (1,2), (2,3), (3,4) will be 1. So we need to delete only 6&7 right?

1 Like

Nope, here they mentioned each and every pair. So, you need to take absolute difference between (1,3) as well as (1,2) and clearly they are different. Similarly we have to do for all rest elements.

1 Like

my bad sorry

It is mentioned that the difference between between each and every pair of elements should be equal .

What is wrong in my code ?

#include
using namespace std;

int main()
{
int T;
cin>>T;
for(int e=0;e<T;e++)
{
int N,b=0,max=0,k,j=0;
cin>>N;
int a[N],s[N];
for(int i=0;i<N;i++)
{
cin>>a[i];
}
if(N<=2)
{
cout<<0<<"\n";
}
else
{
for(int i=0;i<N;i++)
{
a[a[i]%N]=a[a[i]%N]+N;
}
for(int i=0;i<N;i++)
{
if(max<a[i])
{
max=a[i];
k=i;
}
}
for(int i=0;i<N;i++)
{
a[i]=a[i]%N;
}
for(int i=0;i<N;i++)
{
if(a[i]==k)
{
j++;
}
}
if(j==1)
cout<<N-2<<"\n";
else
cout<<N-j<<"\n";
}
}
return 0;
}

I’m not sure why you’re taking the elements modulo N, because modulo has nothing to do with this problem.
For example, on input

1
3
1 4 7

you print 0 but the answer is 1.
If you delete nothing, the array has differences 4-1 = 3 and 7-1 = 6 which are not equal.

Hi !
Why I don’t understand the N-2, if I have a sequences S {1,2,3,4,5}, the max frequence is 1. Well, the answer is 5-2. But {1,2,3} isn’t ok ???

1 Like

N-2 is the number of elements removed, not the number of elements which remain.
Considering your sequence S = \{1, 2, 3, 4, 5\}, removing 5-2 = 3 elements leaves us with two remaining elements, and that’s completely fine.

2 Likes

Thank, I understand !

1 Like

Actually it is a process of finding maximum number in the array you can check this at various blogs. I just want to ask whether anything wrong in my logic.

In this step I converted array
for(int i=0;i<N;i++)
{
a[a[i]%N]=a[a[i]%N]+N;
}
Here I found maximum number
for(int i=0;i<N;i++)
{
if(max<a[i])
{
max=a[i];
k=i;
}
}
Here I converted array in its original form
for(int i=0;i<N;i++)
{
a[i]=a[i]%N;
}

All the test cases passed correctly but answer was not accepted but when I saw editorial I just used same logic but in a different way then what is the problem ?

This blog will give you a clear picture why I used modulo.

Your code definitely doesn’t pass all testcases correctly - I even gave you an example case where it fails above.

As for the blog you linked, the first line says

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k \leq n

k\leq n is important because that isn’t true in this problem - if you look at the constraints you’ll notice that here, k is 10^9.

The latter part of the editorial mentions several ways to count the frequencies of elements of an array which doesn’t depend on how big or small the elements themselves are at all, please try using one of those instead.

How can you say it is not true here ?

Because the problem statement says that 1\leq A_i\leq 10^9 and not 0\leq A_i < n.
The blog states that the array contains elements from 0 to k-1. Would you not agree then that k should be 10^9 + 1 here?

Give me any test case where it fails

I already did that above.

1
3
1 4 7

The answer is 1, not 0 (which is what your code outputs).

1 Like

Thank you. I got it

But there is no other way to count frequency except using hash map in C++ regarding this question ?

You can use a hashmap, you can use a normal (ordered) map, you can even sort the array and iterate over it or use binary search.

Acc to your logic, if the answer is less than N-2, all elements must be equal…
so cant the number be like this
2 6 2 6 2 6
here there is no need to delete any element
please guide if i am wrong!