Count of array elements to be removed to make absolute difference between each pair same

Minimize count of array elements to be removed to maximize difference between any pair up to K

Given an array arr[] consisting of N integers, the task is to find the minimum number of array elements that must be removed such that the absolute difference between each element pair is equal.

Examples:

Input: arr[] = {1, 2}
Output: 0
Explanation: There is only one pair of integers with absolute difference | arr[1] ? arr[2] | = | 1- 2 | = 1. So there is no need to delete any integer from the given array.

Input: arr[] = {2, 5, 1, 2, 2}
Output: 2
Explanation: After deleting 1 and 5, the array A becomes [2, 2, 2] and the absolute difference between each pair of integers is 0.

Approach: The given problem can be solved by counting the frequencies of array elements and print the result based on the following observations:

If the maximum frequency among all the array elements is 1, then all (N – 2) elements must be removed.
Otherwise, the maximum number of array elements that must be removed is (N – maximum frequency) such that all array elements are the same and the difference between any two pairs of elements is the same.

Below is the implementation of the above approach:

C++

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

void countToMakeDiffEqual(int arr[], int n)
{
    // Stores the element having maximum
    // frequency in the array
    int ma = 0;

    unordered_map<int, int> m;

    for (int i = 0; i < n; i++) {
        
        m[arr[i]]++;

        // Find the most occurring element
        ma = max(ma, m[arr[i]]);
    }

    // If only one pair exists then the
    // absolute difference between them
    // will be same
    if (n <= 2)
        cout << 0 << endl;

    else if (ma == 1) {
        cout << n - 2 << endl;
    }

    // Elements to remove is equal to the
    // total frequency minus frequency
    // of most frequent element
    else
        cout << n - ma << endl;
}

// Driver Code
int main()
{
    int arr[] = { 2, 5, 1, 2, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);

    countToMakeDiffEqual(arr, N);

    return 0;
}

Java

// Java program for the above approach
import java.util.HashMap;

class GFG {

    public static void countToMakeDiffEqual(int arr[], int n)
    {
      
        // Stores the element having maximum
        // frequency in the array
        int ma = 0;

        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

        for (int i = 0; i < n; i++) {

            // m[arr[i]]++;
            if (m.containsKey(arr[i])) {
                m.put(arr[i], m.get(arr[i]) + 1);
            } else {
                m.put(arr[i], 1);
            }

            // Find the most occurring element
            ma = Math.max(ma, m.get(arr[i]));
        }

        // If only one pair exists then the
        // absolute difference between them
        // will be same
        if (n <= 2)
            System.out.println(0);

        else if (ma == 1) {
            System.out.println(n - 2);
        }

        // Elements to remove is equal to the
        // total frequency minus frequency
        // of most frequent element
        else
            System.out.println(n - ma);
    }

    // Driver Code
    public static void main(String args[]) {
        int arr[] = { 2, 5, 1, 2, 2 };
        int N = arr.length;

        countToMakeDiffEqual(arr, N);
    }
}

// This code is contributed by gfgking.

Python

# Python 3 program for the above approach
from collections import defaultdict

def countToMakeDiffEqual(arr, n):

    # Stores the element having maximum
    # frequency in the array
    ma = 0

    m = defaultdict(int)

    for i in range(n):

        m[arr[i]] += 1

        # Find the most occurring element
        ma = max(ma, m[arr[i]])

    # If only one pair exists then the
    # absolute difference between them
    # will be same
    if (n <= 2):
        print(0)

    elif (ma == 1):
        print(n - 2)

    # Elements to remove is equal to the
    # total frequency minus frequency
    # of most frequent element
    else:
        print(n - ma)

# Driver Code
if __name__ == "__main__":

    arr = [2, 5, 1, 2, 2]
    N = len(arr)

    countToMakeDiffEqual(arr, N)

    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;

class GFG{

static void countToMakeDiffEqual(int []arr, int n)
{
    // Stores the element having maximum
    // frequency in the array
    int ma = 0;

    Dictionary<int, int> m = new Dictionary<int,int>();

    for (int i = 0; i < n; i++) {
        if(m.ContainsKey(arr[i]))
          m[arr[i]]++;
        else
         m.Add(arr[i],1);

        // Find the most occurring element
        ma = Math.Max(ma, m[arr[i]]);
    }

    // If only one pair exists then the
    // absolute difference between them
    // will be same
    if (n <= 2)
        Console.WriteLine(0);

    else if (ma == 1) {
        Console.WriteLine(n - 2);
    }

    // Elements to remove is equal to the
    // total frequency minus frequency
    // of most frequent element
    else
        Console.WriteLine(n - ma);
}

// Driver Code
public static void Main()
{
    int []arr = { 2, 5, 1, 2, 2 };
    int N = arr.Length;

    countToMakeDiffEqual(arr, N);
}
}

// This code is contributed by ipg2016107.

Javascript

  <script>
        // JavaScript Program to implement
        // the above approach
        function countToMakeDiffEqual(arr, n)
        {
        
            // Stores the element having maximum
            // frequency in the array
            let ma = 0;

            let m = new Map();

            for (let i = 0; i < n; i++) {
                if (m.has(arr[i])) {
                    m.set(arr[i], m.get(arr[i]) + 1);
                }
                else {
                    m.set(arr[i], 1);
                }
                
                // Find the most occurring element
                ma = Math.max(ma, m.get(arr[i]));
            }

            // If only one pair exists then the
            // absolute difference between them
            // will be same
            if (n <= 2) {
                document.write(0 + '<br>');
            }
            else if (ma == 1) {
                document.write(n - 2 + '<br>');
            }

            // Elements to remove is equal to the
            // total frequency minus frequency
            // of most frequent element
            else {
                document.write(n - ma + '<br>');
            }
        }

        // Driver Code
        let arr = [2, 5, 1, 2, 2];
        let N = arr.length;

        countToMakeDiffEqual(arr, N);

     // This code is contributed by Potta Lokesh
    </script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Using Collections:

This solution first counts the frequency of each element in the array using Counter. Then, it finds the most common frequency. If this frequency is 1, it returns len(arr) – 2 if len(arr) > 2, otherwise 0. Otherwise, it returns len(arr) – most_common_freq.

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

// Function to count the minimum number of elements to remove
// to make all differences equal in the array
int countToMakeDiffEqual(vector<int>& arr) {
    // Create an unordered_map to store the frequency of each element
    unordered_map<int, int> counter;
    for (int num : arr) {
        counter[num]++;
    }

    // Find the most common frequency in the array
    int mostCommonFreq = 0;
    for (auto& pair : counter) {
        mostCommonFreq = max(mostCommonFreq, pair.second);
    }

    // Calculate the count needed to make all differences equal
    if (mostCommonFreq == 1) {
        return arr.size() > 2 ? arr.size() - 2 : 0;
    } else {
        return arr.size() - mostCommonFreq;
    }
}

// Main function to test the countToMakeDiffEqual function
int main() {
    // Sample array
    vector<int> arr = {2, 5, 1, 2, 2};

    // Print the result of countToMakeDiffEqual function
    cout << countToMakeDiffEqual(arr) << endl;

    return 0;
}

// This code is contributed by Shivam Gupta

Java

import java.util.*;

public class CountToMakeDiffEqual {
    // Function to count the minimum number of elements to remove
    // to make all differences equal in the array
    public static int countToMakeDiffEqual(int[] arr) {
        // Create a HashMap to store the frequency of each element
        Map<Integer, Integer> counter = new HashMap<>();
        for (int num : arr) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        // Find the most common frequency in the array
        int mostCommonFreq = 0;
        for (int freq : counter.values()) {
            mostCommonFreq = Math.max(mostCommonFreq, freq);
        }

        // Calculate the count needed to make all differences equal
        if (mostCommonFreq == 1) {
            return arr.length > 2 ? arr.length - 2 : 0;
        } else {
            return arr.length - mostCommonFreq;
        }
    }

    // Main method to test the countToMakeDiffEqual function
    public static void main(String[] args) {
        // Sample array
        int[] arr = {2, 5, 1, 2, 2};

        // Print the result of countToMakeDiffEqual function
        System.out.println(countToMakeDiffEqual(arr));
    }
}

// This code is contributed by Akshita

Python

from collections import Counter


def count_to_make_diff_equal(arr):
    counter = Counter(arr)
    most_common_freq = counter.most_common(1)[0][1]
    if most_common_freq == 1:
        return len(arr) - 2 if len(arr) > 2 else 0
    return len(arr) - most_common_freq


# Driver Code
if __name__ == "__main__":
    arr = [2, 5, 1, 2, 2]
    print(count_to_make_diff_equal(arr))

JavaScript

// Function to count the minimum number of elements to remove
// to make all differences equal in the array
function countToMakeDiffEqual(arr) {
    // Create an object to store the frequency of each element
    let counter = {};
    arr.forEach(num => {
        counter[num] = (counter[num] || 0) + 1;
    });

    // Find the most common frequency in the array
    let mostCommonFreq = 0;
    Object.values(counter).forEach(freq => {
        mostCommonFreq = Math.max(mostCommonFreq, freq);
    });

    // Calculate the count needed to make all differences equal
    if (mostCommonFreq === 1) {
        return arr.length > 2 ? arr.length - 2 : 0;
    } else {
        return arr.length - mostCommonFreq;
    }
}

// Main method to test the countToMakeDiffEqual function
function main() {
    // Sample array
    let arr = [2, 5, 1, 2, 2];

    // Print the result of countToMakeDiffEqual function
    console.log(countToMakeDiffEqual(arr));
}

// Call the main method
main();

Output

Time Complexity: O(N)

Space Complexity: O(N)

Tags:

#frequency-counting #HashTable #Arrays #DSA #Hash #Mathematical #Arrays #Hash #Mathematical

Minimize count of array elements to be removed to maximize difference between any pair up to K

Count of array elements to be removed to make absolute difference between each pair same

Using Collections:

Contact Us