Given an array arr[] consisting of N integers, the task is to split the array into the minimum number of disjoint groups, such that differences between any pair of the elements in a group are equal to the difference between their positions in that group.
Examples:
Input: arr[] = {30, 32, 44, 31, 45, 32, 31, 33}
Output: 3
Explanation:
The one possible way to split the array is:
- First group: {30, 31, 32, 33}
- Second group: {31, 32}
- Third group: {44, 45}
Therefore, the number of groups is 3, which is the minimum number of groups in which the array can be split satisfying the conditions.
Input: arr[] = {1, 5, 3, 1, 7, 7, 9}
Output: 7
Naive Approach: The simplest approach is, split the array into K subsets for every integer K less than or equal to N, and then check if all the subsets of the array satisfy the given conditions or not. If found to be true, then print the minimum size of the partition possible.
Time Complexity: O(N(N + 2))
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the observation that the elements in each group must be sorted and the difference between adjacent elements should be 1. Follow the steps below to solve the problem:
- Sort the given array in ascending order.
- Initialize a Map, say mp to store the frequency of array elements.
- Initialize a variable, say count as 0 to store the count of the minimum number of disjoint groups formed.
- Traverse the given array arr[], and increment the frequency of each element in the map mp.
- Traverse the given array arr[], using the variable i, and perform the following steps:
- If the count of arr[i] in map mp is at least 1, and the count of (arr[i] – 1) in the map mp then:
- Increment the value of count by 1.
- Iterate until the count of arr[i] in mp is greater than 0 and in each iteration, decrement mp[arr[i]] by 1 and increment arr[i] by 1.
- If the count of arr[i] in map mp is at least 1, and the count of (arr[i] – 1) in the map mp then:
- Finally, after completing the above steps, print the value of the count as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to split the array into// minimum number of disjoint groups// satisfying the conditionsint numberOfSplit(int arr[], int N){ // Sort the array in ascending order sort(arr, arr + N); // Stores frequency of array elements unordered_map<int, int> mp; // Traverse the array, arr[] for (int i = 0; i < N; i++) mp[arr[i]]++; // Stores the number of groups int count = 0; // Traverse the array, arr[] for (int i = 0; i < N; i++) { // If mp[arr[i]] is at least 1 // and mp[arr[i]-1] is 0 if (mp[arr[i]] > 0 && mp[arr[i] - 1] == 0) { // Increment the count by 1 count++; // Iterate until mp[arr[i]] // is greater than 0 while (mp[arr[i]] != 0) { // Decrement mp[arr[i]] // by 1 mp[arr[i]]--; // Increment arr[i] by 1 arr[i]++; } } } // Return the resultant count return count;}// Driver Codeint main(){ int arr[] = { 30, 32, 44, 31, 45, 32, 31, 33 }; int N = sizeof(arr) / sizeof(arr[0]); cout << numberOfSplit(arr, N); return 0;} |
Python3
# Python program for the above approach# Function to split the array into# minimum number of disjoint groups# satisfying the conditionsdef numberOfSplit(arr, N): # Sort the array in ascending order arr.sort() # Stores frequency of array elements mp = {} # Traverse the array, arr[] for i in range(N): if(arr[i] in mp): mp[arr[i]] = mp[arr[i]]+1 else: mp[arr[i]] = 1 # Stores the number of groups count = 0 # Traverse the array, arr[] for i in range(N): # If mp[arr[i]] is at least 1 # and mp[arr[i]-1] is 0 if (arr[i] in mp and mp[arr[i]]>0 and ((arr[i] - 1) not in mp or ((arr[i]-1) in mp and mp[arr[i]-1]==0))): # Increment the count by 1 count += 1 # Iterate until mp[arr[i]] # is greater than 0 while arr[i] in mp and mp[arr[i]] > 0: # Decrement mp[arr[i]] # by 1 mp[arr[i]] = mp[arr[i]] - 1 # Increment arr[i] by 1 arr[i] += 1 # Return the resultant count return count# Driver Codearr = [30, 32, 44, 31, 45, 32, 31, 33]N = len(arr)print(numberOfSplit(arr, N))# This code is contributed by shinjanpatra. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to split the array into// minimum number of disjoint groups// satisfying the conditionsstatic int numberOfSplit(int []arr, int N){ // Sort the array in ascending order Array.Sort(arr); // Stores frequency of array elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array, arr[] for(int i = 0; i < N; i++) { if (mp.ContainsKey(arr[i])) mp[arr[i]] += 1; else mp.Add(arr[i], 0); } // Stores the number of groups int count = 2; // Traverse the array, arr[] for(int i = 0; i < N; i++) { // If mp[arr[i]] is at least 1 // and mp[arr[i]-1] is 0 if (mp[arr[i]] > 0 && mp[arr[i] - 1] == 0) { // Increment the count by 1 count++; // Iterate until mp[arr[i]] // is greater than 0 while (mp[arr[i]] != 0) { // Decrement mp[arr[i]] // by 1 mp[arr[i]]--; // Increment arr[i] by 1 arr[i]++; } } } // Return the resultant count return count;}// Driver Codepublic static void Main(){ int []arr = { 30, 32, 44, 31, 45, 32, 31, 33 }; int N = arr.Length; Console.Write(numberOfSplit(arr, N));}}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to split the array into // minimum number of disjoint groups // satisfying the conditions static int numberOfSplit(int[] arr, int N) { // Sort the array in ascending order Arrays.sort(arr); // Stores frequency of array elements Map<Integer, Integer> mp = new HashMap<>(); // Traverse the array, arr[] for (int i = 0; i < N; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 0); } } // Stores the number of groups int count = 2; // Traverse the array, arr[] for (int i = 0; i < N; i++) { // If mp[arr[i]] is at least 1 // and mp[arr[i]-1] is 0 if (mp.get(arr[i]) > 0 && mp.get(arr[i] - 1) == 0) { // Increment the count by 1 count++; // Iterate until mp[arr[i]] // is greater than 0 while (mp.get(arr[i]) != 0) { // Decrement mp[arr[i]] // by 1 mp.put(arr[i], mp.get(arr[i]) - 1); // Increment arr[i] by 1 arr[i]++; } } } // Return the resultant count return count; } // Driver Code public static void main(String[] args) { int[] arr = {30, 32, 44, 31, 45, 32, 31, 33}; int N = arr.length; System.out.println(numberOfSplit(arr, N)); }} |
Javascript
<script>// Javascript program for the above approach// Function to split the array into// minimum number of disjoint groups// satisfying the conditionsfunction numberOfSplit(arr, N){ // Sort the array in ascending order arr.sort(); // Stores frequency of array elements var mp = new Map(); // Traverse the array, arr[] for (var i = 0; i < N; i++) { if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1) } // Stores the number of groups var count = 0; // Traverse the array, arr[] for (var i = 0; i < N; i++) { // If mp[arr[i]] is at least 1 // and mp[arr[i]-1] is 0 if (mp.has(arr[i]) && mp.get(arr[i])>0 && (!mp.has(arr[i] - 1) || (mp.has(arr[i]-1) && mp.get(arr[i]-1)==0))) { // Increment the count by 1 count++; // Iterate until mp[arr[i]] // is greater than 0 while (mp.get(arr[i]) > 0) { // Decrement mp[arr[i]] // by 1 mp.set(arr[i], mp.get(arr[i])-1); // Increment arr[i] by 1 arr[i]++; } } } // Return the resultant count return count;}// Driver Codevar arr = [30, 32, 44, 31, 45, 32, 31, 33];var N = arr.length;document.write(numberOfSplit(arr, N));// This code is contributed by itsok.</script> |
Output
3
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
