# Split Array into min number of subsets with difference between each pair greater than 1

Given an array **arr[]** of size **N**, the task is to split the array into a **minimum **number of subset such that each pair of elements in each subset have the difference strictly greater than 1.**Note: **All elements in the array are distinct.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr = {5, 10, 6, 50}Output:2Explanation:

Possible partitions are: {5, 10, 50}, {6}

Input:arr = {2, 4, 6}Output:1Explanation:

Possible partitions are: {2, 4, 6}

**Approach:** The idea is to observe that if there is no such pair **i**, **j** such that **|arr[i] – arr[j]| = 1**, then it is possible to put all the elements in the same partition, otherwise divide them into two partitions. So the required minimum number of partitions is always **1 **or **2**.

- Sort the given array.
- Compare the adjacent elements. If at any point their difference to be equal to 1, then print
**“2”**as the required number of subset partition will always be 2 as we can put one of the elements from the above pair into another subset. - If we traversed all the array didn’t found any adjacent pair with a difference less than 2 then print
**“1”**without splitting the array into subsets we can have all possible pairs difference at least 2.

Below is the implementation for 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 subsets with` `// difference strictly > 1` `void` `split(` `int` `arr[], ` `int` `n)` `{` ` ` `// Sort the array` ` ` `sort(arr, arr + n);` ` ` `int` `count = 1;` ` ` `// Traverse through the sorted array` ` ` `for` `(` `int` `i = 1; i < n; i++) {` ` ` `// Check the pairs of elements` ` ` `// with difference 1` ` ` `if` `(arr[i] - arr[i - 1] == 1) {` ` ` `// If we find even a single` ` ` `// pair with difference equal` ` ` `// to 1, then 2 partitions` ` ` `// else only 1 partition` ` ` `count = 2;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Print the count of partitions` ` ` `cout << count << endl;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given array` ` ` `int` `arr[] = { 2, 4, 6 };` ` ` `// Size of the array` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(` `int` `);` ` ` `// Function Call` ` ` `split(arr, n);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` ` ` `// Function to split the array into` `// minimum number of subsets with` `// difference strictly > 1` `static` `void` `split(` `int` `arr[], ` `int` `n)` `{` ` ` ` ` `// Sort the array` ` ` `Arrays.sort(arr);` ` ` `int` `count = ` `1` `;` ` ` `// Traverse through the sorted array` ` ` `for` `(` `int` `i = ` `1` `; i < n; i++)` ` ` `{` ` ` ` ` `// Check the pairs of elements` ` ` `// with difference 1` ` ` `if` `(arr[i] - arr[i - ` `1` `] == ` `1` `)` ` ` `{` ` ` ` ` `// If we find even a single` ` ` `// pair with difference equal` ` ` `// to 1, then 2 partitions` ` ` `// else only 1 partition` ` ` `count = ` `2` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Print the count of partitions` ` ` `System.out.print(count);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` ` ` `// Given array` ` ` `int` `arr[] = { ` `2` `, ` `4` `, ` `6` `};` ` ` `// Size of the array` ` ` `int` `n = arr.length;` ` ` `// Function call` ` ` `split(arr, n);` `}` `}` `// This code is contributed by jrishabh99` |

## Python3

`# Python3 implementation of` `# the above approach` `# Function to Split the array into` `# minimum number of subsets with` `# difference strictly > 1` `def` `split(arr, n):` ` ` `# Sort the array` ` ` `arr.sort()` ` ` `count ` `=` `1` ` ` `# Traverse through the sorted array` ` ` `for` `i ` `in` `range` `(` `1` `, n):` ` ` `# Check the pairs of elements` ` ` `# with difference 1` ` ` `if` `(arr[i] ` `-` `arr[i ` `-` `1` `] ` `=` `=` `1` `):` ` ` `# If we find even a single` ` ` `# pair with difference equal` ` ` `# to 1, then 2 partitions` ` ` `# else only 1 partition` ` ` `count ` `=` `2` ` ` `break` ` ` `# Print the count of partitions` ` ` `print` `(count)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `# Given array` ` ` `arr ` `=` `[ ` `2` `, ` `4` `, ` `6` `]` ` ` `# Size of the array` ` ` `n ` `=` `len` `(arr)` ` ` `# Function call` ` ` `split(arr, n)` `# This code is contributed by Shivam Singh` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` ` ` `// Function to split the array into` `// minimum number of subsets with` `// difference strictly > 1` `static` `void` `split(` `int` `[]arr, ` `int` `n)` `{` ` ` `// Sort the array` ` ` `Array.Sort(arr);` ` ` `int` `count = 1;` ` ` ` ` `// Traverse through the sorted array` ` ` `for` `(` `int` `i = 1; i < n; i++)` ` ` `{` ` ` ` ` `// Check the pairs of elements` ` ` `// with difference 1` ` ` `if` `(arr[i] - arr[i - 1] == 1)` ` ` `{` ` ` `// If we find even a single` ` ` `// pair with difference equal` ` ` `// to 1, then 2 partitions` ` ` `// else only 1 partition` ` ` `count = 2;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` ` ` `// Print the count of partitions` ` ` `Console.Write(count);` `}` ` ` `// Driver Code` `public` `static` `void` `Main(` `string` `[] args)` `{` ` ` ` ` `// Given array` ` ` `int` `[] arr = ` `new` `int` `[]{ 2, 4, 6 };` ` ` ` ` `// Size of the array` ` ` `int` `n = arr.Length;` ` ` ` ` `// Function call` ` ` `split(arr, n);` `}` `}` ` ` `// This code is contributed by Ritik Bansal` |

## Javascript

`<script>` `// Javascript program for` `// the above approach` `// Function to split the array into` `// minimum number of subsets with` `// difference strictly > 1` `function` `split(arr, n)` `{` ` ` ` ` `// Sort the array` ` ` `arr.sort();` ` ` `let count = 1;` ` ` ` ` `// Traverse through the sorted array` ` ` `for` `(let i = 1; i < n; i++)` ` ` `{` ` ` ` ` `// Check the pairs of elements` ` ` `// with difference 1` ` ` `if` `(arr[i] - arr[i - 1] == 1)` ` ` `{` ` ` ` ` `// If we find even a single` ` ` `// pair with difference equal` ` ` `// to 1, then 2 partitions` ` ` `// else only 1 partition` ` ` `count = 2;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` ` ` `// Prlet the count of partitions` ` ` `document.write(count);` `}` ` ` `// Driver Code` ` ` ` ` `// Given array` ` ` `let arr = [ 2, 4, 6 ];` ` ` ` ` `// Size of the array` ` ` `let n = arr.length;` ` ` ` ` `// Function call` ` ` `split(arr, n);` `</script>` |

**Output:**

1

**Time Complexity:** O(N log N), where N is the length of the array.**Auxiliary Space:** O(1)