Count Maximum Elements of Array with Absolute Difference ≤ K in C++

We are given an array let’s say, arr[] of integer elements of any given size and a positive integer k and the task is to calculate the count of those element pairs whose absolute difference doesn’t exceed the given integer k.

Arrays a kind of data structure that can store a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.

For example

Input − int arr[] = {2, 3, 6, 12, 14}, k= 5
Output − count is : 3

Explanation − the pairs with maximum absolute difference not more then k i.e. 5 in this example the pairs so formed are: (2, 3), (2, 6), (3,6) i.e {2, 3, 6} therefore the count is 3.

Input − int arr[] = {2, 3, 6, 12, 14}, k= 10
Output − count is : 4

Explanation − the pairs with maximum absolute difference not more then k i.e. 10 in this example the pairs so formed are: (2, 3), (2, 6), (3,6), (2, 12), (3, 12), (6, 12) i.e {2, 3, 6, 12} therefore the count is 4 as the maximum elements are 4.

Input − int arr[] = {2, 3, 6, 12, 14}, k= 0
Output − count is : 0

Explanation − As there is no pair with difference as 0 so count is 0.

Approach used in the below program is as follows

• Create an array let’s say, arr[] and a positive integer k

• Calculate the length of an array using the length() function that will return an integer value as per the elements in an array.

• Take a temporary variable that will store the count of elements.

• Declare two temporary variables lets say, first and last and initialise with 0

• Call the sort method to sort an array and pass array and size of an array as an argument to the function.

• Start loop for i to 0 and i less than size of an array

• Inside the loop, start while j<size AND arr[j] <= arr[i] + k

• Inside while, check IF count < j-i then set count to j - i and first to i and last to j

• Return the count

• Print the result.

Example

 Live Demo

#include <iostream>
#include <algorithm>
using namespace std;
int countmax(int arr[], int size, int K){
   int result = 0;
   int i = 0, j = 0;
   int beg = 0;
   int end = 0;
   // Sort the array
   sort(arr, arr + size);
   // Find max elements
   for (i = 0; i < size; i++) {
      // Count all elements which are in the range
      while (j < size && arr[j] <= arr[i] + K)
      j++;
      if (result < (j - i)) {
         result = (j - i);
         beg = i;
         end = j;
      }
   }
   // Return the max count
   return result;
}
// main function
int main(){
   int arr[] = { 2, 3, 6, 12, 14 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int K = 5;
   cout <<"count is "<<countmax(arr, size, K) << endl;
   return 0;
}

Output

If we run the above code we will get the following output −

count is 3