Minimum number of subsets with distinct elements in Java

An array with n elements is provided to you. Divide the array into smaller groups so that no group contains duplicate entries. Determine the minimum number of subsets that can be made. Observe the following examples.

Example 1:

Input : arr[] = {1, 2, 3, 4}

Output :1

Explanation:  In this subset, all values are distinct

Example 2:

Input:  arr[] = { 5, 6, 9, 3, 4, 3, 4 };

Output: 2

Explanation: We must create two subsets {5,6,9,3,4} and {3,4} such that subsets have distinct elements.

We need to identify the most common element in the array. The frequency of the most common element is represented in the result.

Approach: Frequency counting with a sorted array

Frequency counting with a sorted array is a technique used to count the number of occurrences of each element in a given array, assuming the array is sorted in ascending order. The technique involves iterating through the sorted array and keeping track of the count of each element. Several problems can be addressed using the Method of frequency counting on sorted arrays, including but not limited to identifying duplicates, determining the most commonly occurring element, and calculating the minimum number of subsets with unique elements.

Algorithm :

1. Sort the input array using Arrays.sort() method.
2. Initialize variables maxCount and currentCount to 1.
3. Traverse the sorted array starting from the second element.
4. If the current element is the same as the last element, increment the currentCount.
5. If the current element differs from the previous element, update the maxCount with the maximum of maxCount and currentCount, and reset the currentCount to 1.
6. Return the maximum of maxCount and currentCount, the minimum number of subsets with distinct elements.

Implementation:

Filename: SubsetDistinctElements.java

import java.util.Arrays;
public class SubsetDistinctElements {
    
    //Method to count the minimum number of subsets with distinct elements in an array
    public static int countSubsets(int[] arr) {
        // Sort the input array
        Arrays.sort(arr);
        
        // Initialize variables to keep track of the maximum and current count
        int maxCount = 1, currentCount = 1;
        
        // Traverse the sorted array
        for (int i = 1; i < arr.length; i++) {
            // If the current element is the same as the previous one, increment the count
            if (arr[i] == arr[i - 1]) {
                currentCount++;
            } else { // If the current element is different from the previous one, update the maximum count and reset the current count to 1
                maxCount = Math.max(maxCount, currentCount);
                currentCount = 1;
            }
        }
        // Return the maximum count, which is the minimum number of subsets with distinct elements
        return Math.max(maxCount, currentCount);
    }


    public static void main(String[] args) {
        // Sample input array
        int[] arr = { 8, 3, 7, 1, 5, 1, 5 };
        // Call the countSubsets Method to find the minimum number of subsets with distinct elements
        int subsets = countSubsets(arr);
        // Print the result
        System.out.println("Minimum number of subsets with distinct elements: " + subsets);
    }
}

Output:

Minimum number of subsets with distinct elements: 2

Complexity Analysis: The time complexity of the program is O(nlogn), where n is the length of the input array. The time complexity of the program is O(nlogn) in the worst case, primarily due to the sorting operation. The sorting operation is executed using the Arrays.sort() Method. The for loop that traverses the sorted array takes O(n) time in the worst case.

The space complexity of the program is O(1), as it uses only a constant amount of additional space to keep track of the maximum and current counts. Therefore, the program uses a small amount of memory and is space efficient.

Approach: Hashing-based frequency counting

Hashing-based frequency counting is an approach to counting the number of occurrences of elements in a given array or dataset using a hash table. In this technique, a hash table is created to store the frequencies of each element. The frequency of each element is incremented whenever the element is encountered while traversing the array.

Algorithm:

1. Create an empty hash table to store the frequencies of elements.
2. Traverse the input array and for each element: a. If it exists in the hash table, increment its frequency by 1. b. If it does not exist in the hash table, add it with a frequency of 1.
3. Find the maximum frequency in the hash table.
4. Return the maximum frequency, the minimum number of subsets with distinct elements.

Implementation

Filename: SubsetDistinctElements2.java

import java.util.HashMap;
public class SubsetDistinctElements2 {
    //Method to count the minimum number of subsets with distinct elements in an array
    public static int countSubsets(int[] arr) {
        // Create a hash table to store frequencies of elements
        HashMap<Integer, Integer> freq = new HashMap<>();
        
        // Traverse the input array and update frequencies in the hash table
        for (int i = 0; i < arr.length; i++) {
            int element = arr[i];
            if (freq.containsKey(element)) {
                freq.put(element, freq.get(element) + 1);
            } else {
                freq.put(element, 1);
            }
        }
        
        // Find the maximum frequency in the hash table
        int maxCount = 1;
        for (int count : freq.values()) {
            maxCount = Math.max(maxCount, count);
        }
        
        // Return the maximum count, which is the minimum number of subsets with distinct elements
        return maxCount;
    }


    public static void main(String[] args) {
        // Sample input array
        int[] arr = { 8, 3, 7, 1, 5, 1, 5 };
        // Call the countSubsets Method to find the minimum number of subsets with distinct elements
        int subsets = countSubsets(arr);
        // Print the result
        System.out.println("Minimum number of subsets with distinct elements: " + subsets);
    }
}

Output:

Minimum number of subsets with distinct elements: 2

Complexity Analysis:

The time complexity of the countSubsets() Method is O(n), where n is the size of the input array. It is because we traverse the input array once and update the hash table with the frequency of each element, which takes constant time for each element.

The space complexity of the countSubsets() Method is O(n), where n is the size of the input array. It is because we store the frequency of each element in the hash table, which could have up to n entries if all elements are distinct.

Approach: Using Recursion

Recursion is a programming technique where a method calls itself to solve a problem. It is a powerful and flexible tool that allows for elegant solutions to complex problems. To find the minimum number of subsets with distinct elements in an array, the approach involves recursively dividing the array into subarrays and computing the minimum number of such subsets for each subarray. The approach involves sorting the array and recursively dividing it into subarrays.

Filename: SubsetDistinctElements4.java

// The program uses recursion to count the minimum number of subsets with distinct elements from an array of integers
import java.util.Arrays;


public class SubsetDistinctElements4 {




public static void main(String[] args) {
    int[] arr = { 8, 3, 7, 1, 5, 1, 5 };
    int subsets = countSubsets(arr);
    System.out.println("Minimum number of subsets with distinct elements: " + subsets);
}


// Wrapper method that sorts the array and calls the recursive Method
public static int countSubsets(int[] arr) {
    Arrays.sort(arr);
    return countSubsetsRecursive(arr, 0, arr.length - 1);
}


// Recursive Method that finds the minimum number of subsets with distinct elements
private static int countSubsetsRecursive(int[] arr, int left, int right) {
    // Base case: If there are no elements left in the array, return 0
    if (left > right) {
        return 0;
    }
    
    // Find the index of the last occurrence of the current element in the sorted array
    int i = left;
    while (i < right && arr[i] == arr[i + 1]) {
        i++;
    }
    
    // The minimum number of subsets with distinct elements for the current subarray is
    // 1 (the current element) plus the minimum number of subsets in the subarrays
    // to the right and left of the current element
    int count = 1 + Math.min(countSubsetsRecursive(arr, i + 1, right),
            countSubsetsRecursive(arr, left, i - 1));
    return count;
}
}

Output:

Minimum number of subsets with distinct elements: 2

Complexity Analysis:

The algorithm's time complexity is O(2^n), where n is the number of elements in the array. The algorithm's high time complexity is its consideration of every possible subset of the array. The number of possible subsets can be as much as 2^n, where n is the number of elements in the array.

The space complexity of the algorithm is O(n), where n is the number of elements in the array.