Header Ads Widget

Equal differences | codechef solution

Rajnish Tripathi 15:09

 Problem :-

Read problems statements in Mandarin Chinese, Russian, and Bengali as well.

You are given an array of � integers. Find the minimum number of integers you need to delete from the array such that the absolute difference between each pair of integers in the remaining array will become equal.

Input Format

  • The first line of input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains an integer �.
  • The second line of each test case contains � space-separated integers �1,�2,…,��.

Output Format

For each test case, print a single line containing one integer - the minimum number of integers to be deleted to satisfy the given condition.

Constraints

  • 1≤�≤104
  • 1≤�≤105
  • 1≤��≤109
  • Sum of � over all test cases does not exceed 5⋅105.

Sample 1:

Input
Output
3
2
1 2
5
2 5 1 2 2
4
1 2 1 2
0
2
2

Explanation:

Test case 1: There is only one pair of integers and the absolute difference between them is ∣�1−�2∣=∣1−2∣=1. So there is no need to delete any integer from the given array.

Test case 2: If the integers 1 and 5 are deleted, the array A becomes [2,2,2] and the absolute difference between each pair of integers is 0. There is no possible way to delete less than two integers to satisfy the given condition.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define l long
int main() {
  // your code goes here
  int t;
  cin>>t;
  while(t--)
  {
   l l int n;
   cin>>n;
   l l int s[n];
   unordered_map<l l int,l l int>m;
   for(l l int i=0;i<n;i++)
   {
   cin>>s[i];
   m[s[i]]++;
  
  
   }
   long long int maax=0;
   for(auto i:m)
   {
   if(maax<i.second)
   maax=i.second;
   }
   if(n==1||n==2)
   cout<<"0\n";
   else if(maax!=1)
   {
   cout<<(n-maax)<<endl;
  
   }
   else cout<<(n-2)<<endl;
  
  }
  return 0;
}


Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-








Tags:

Post a Comment

0 Comments