MODEQUAL - Unofficial Editorial

editorial
,
1

Insights

  1. The Maximum Number of operations) would be n to make every number equal.
    i.e if we modulo every a_i with 1

  2. When we take modulo with a positive number M,
    we can get number from range [0, min( a_i, M))
    i.e if M > a_i => a_i \% M = a_i \ \ \ \ for eg: 1 % 2 = 1

  3. You cannot get a bigger number from a smaller number after doing modulo operation with a positive number M

  4. So the best we can do is try to make every number equal to the smallest number.

  5. If we can’t make every number after operation equal to the smallest number; then we would have to do n operation.
    Reason: We need to find a number smaller than the smallest number, so in-turn we would have to do operations on the smallest number and all the numbers greater than the smallest number.

Algorithm

  1. Find the minimum element from the array
  2. Loop through the array.
  3. if arr[i] == min_element continue (we don’t need to perform operations on this element since its already the smallest element)
  4. Check if you can get the min_element from the current element
    if (arr[i] % (arr[i] - min_element)) == min_element

Code (function Snippet)

int ModEquality(vector<int> &arr)
{
  int n = arr.size();
  int num = *min_element(arr.begin(), arr.end());
  int count = 0;

  for (int el : arr)
  {
    if (el == num)
      continue;
    else
    {
      int modular = el - num;
      if (el % modular != num)
        return n;
      else
        count++;
    }
  }
  return count;
}
2 Likes
3 
void solve(){
    int n; cin >> n;
	vector<int> arr(n);
	for(int i=0; i<n; i++) cin >> arr[i];
	int mn = *min_element(arr.begin(), arr.end());
	int c = count(arr.begin(), arr.end(), mn);
	if(mn == 0){
	    cout << n - c << endl;   
	    return;
	}
	for(int i=0; i<n; i++){
	    if(arr[i] == mn) continue;
		if(arr[i] <= 2*mn){
			cout << n << endl;
			return;
		}
	}
	cout << n-c << endl;
}

Could you plz tell me on which TestCase my logic is failing.
I am just checking whether the minimum no is zero? If yes, just convert every other number to zero.
If not, then check if there is any other number <= 2*minimum? Bcz if we want remainder equals to min, we have to have the divisor greater than the min and if the number is less than 2*min then it’s not possible to have the remainder equals to min.

4

I went through your solution and also tried it on my local ide with different test cases, I can’t seem to find what’s wrong with this solution, it should work according to me :frowning:

1 Like
5

There is int overflow when you do 2*mn.
Test Case:-
2
1999999999 2000000000

1 Like