Given an array arr[] of size n, the task is to find the maximum possible size x of a group such that the difference between any pair formed in the group differ by at most 5.
Examples:
Input: arr[] = {1, 10, 17, 12, 15, 2}
Output: 3
Explanation: You can create a group with [12, 17, 15]. [10, 12, 15] is also the valid group. Hence, the maximum possible size is 3Input: arr[] = {13, 13, 13, 13, 13, 13, 13, 13, 13, 13}
Output: 10
Explanation: The difference between each pair of elements is 0 always. You can make the group with all the elements. Hence, the maximum possible size is 10
Approach: Implement the idea below to solve the problem:
This problem can be solved using binary search. In order to have the maximum possible size such that no pair differ more than 5, We will sort out the array first and start iterating and calculate the range upto which the each pair has a difference less than or equal to 5. In order to calculate the range we can use the upper bound. Also, comparing the previous maximum possible size with the current size in each iteration.
Follow the steps mentioned below to implement the idea:
- Sort the array.
- Initialized a variable maxi to 1 that stores the maximum possible size
- Start iterating the array from starting
- Calculate the maximum possible range up to which the difference between each pair is less than or equal to 5.
- We will be using upper_bound(arr.begin(), arr.end(), arr[i] + 5) – arr.begin() in order to calculate the maximum possible range.
- The current size will be calculated as idx – current index.
- Store the maximum possible size in each iteration by comparing the current size with the previous maximum size.
- Return maxi.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function for calculating the// maximum possible sizeint maximum_possible(vector<int>& arr, int n){ // sort the array sort(arr.begin(), arr.end()); // Declare a variable that stores // the maximum size int maxi = 1; for (int i = 0; i < n; i++) { // Calculating the range upto which // the difference is at most 5 int idx = upper_bound(arr.begin(), arr.end(), arr[i] + 5) - arr.begin(); // Storing the maximum size // in each iteration maxi = max(maxi, idx - i); } // Returning the maximum possible size return maxi;}// Driver codeint main(){ vector<int> arr = { 1, 10, 17, 12, 15, 2 }; int n = arr.size(); // Function call cout << maximum_possible(arr, n); return 0;} |
Java
// Java code for the above approach:import java.util.*;public class GFG { // Function for calculating the // maximum possible size public static int maximum_possible(List<Integer> arr, int n) { // Sort the array Collections.sort(arr); // Declare a variable that stores the maximum size int maxi = 1; for (int i = 0; i < n; i++) { // Calculating the range upto which the // difference is at most 5 int idx = Collections.binarySearch( arr, arr.get(i) + 5); // If the element is not found, binarySearch() // returns (-(insertion point) - 1) So, we take // the absolute value of that and subtract 1 to // get the index if (idx < 0) { idx = -(idx + 1) - 1; } // Storing the maximum size in each iteration maxi = Math.max(maxi, idx - i + 1); } // Returning the maximum possible size return maxi; } public static void main(String[] args) { List<Integer> arr = Arrays.asList(1, 10, 17, 12, 15, 2); int n = arr.size(); // Function call System.out.println(maximum_possible(arr, n)); }} |
Python3
# Python code for the above approach:import bisect# Function for calculating the # maximum possible sizedef maximum_possible(arr, n): # Sort the array arr.sort() # Declare a variable that stores # the maximum size maxi = 1 for i in range(n): # Calculating the range upto which # the difference is at most 5 idx = bisect.bisect_right(arr, arr[i] + 5) # If the element is not found, bisect_right() # returns the insertion point. So, we subtract 1 to # get the index if idx == 0: idx = 1 else: idx -= 1 # Storing the maximum size in each iteration maxi = max(maxi, idx - i + 1) # Returning the maximum possible size return maxi arr = [1, 10, 17, 12, 15, 2]n = len(arr)# Function callprint(maximum_possible(arr, n))# This code is contributed by Prasad Kandekar(prasad264) |
C#
// C# code for the above approach:using System;using System.Linq;public class Program { // Function for calculating the // maximum possible size public static int MaximumPossible(int[] arr, int n) { // sort the array Array.Sort(arr); // Declare a variable that stores // the maximum size int maxi = 1; for (int i = 0; i < n; i++) { // Calculating the range upto which // the difference is at most 5 int idx = Array.BinarySearch( arr, i + 1, n - i - 1, arr[i] + 5); if (idx < 0) { idx = ~idx - 1; } // Storing the maximum size // in each iteration maxi = Math.Max(maxi, idx - i + 1); } // Returning the maximum possible size return maxi; } // Driver code public static void Main() { int[] arr = new int[] { 1, 10, 17, 12, 15, 2 }; int n = arr.Length; // Function call Console.WriteLine(MaximumPossible(arr, n)); }}// This code is contributed by rutikbhosale |
Javascript
<script>// Javascript program for above approach// Function for calculating the maximum possible sizefunction maximum_possible(arr, n) { // Sort the array arr.sort((a, b) => a - b); // Define a function to find the upper bound using binary search function upper_bound(arr, key) { let left = 0; let right = arr.length; while (left < right) { let mid = Math.floor((left + right) / 2); if (arr[mid] <= key) { left = mid + 1; } else { right = mid; } } return left; } // Declare a variable that stores the maximum size let maxi = 1; for (let i = 0; i < n; i++) { // Calculating the range upto which the difference is at most 5 let idx = upper_bound(arr, arr[i] + 5); // Storing the maximum size in each iteration maxi = Math.max(maxi, idx - i); } // Returning the maximum possible size return maxi;}// Driver codelet arr = [1, 10, 17, 12, 15, 2];let n = arr.length;// Function callconsole.log(maximum_possible(arr, n));// this code is contributed by bhardwajji</script> |
Output
3
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Alternative Approach:
Implement the idea below to solve the problem:
Use a sliding window to maintain a subarray where the difference between any two elements is less than or equal to 5. Start with a subarray consisting of only the first element, and then expand the window by incrementing j until the difference between arr[j] and arr[i] is less than or equal to 5. Once the window is expanded as much as possible, calculate its size and update the maxLength accordingly. Then increment i until the difference between arr[j] and arr[i] is greater than 5, which means need to contract the window. Continue this process until j reaches the end of the array.
Follow the steps mentioned below to implement the idea:
- Sort the array.
- Initialize two pointers i and j, both pointing to the first element in the array.
- Initialize a variable ‘maxLength’ to 1 to keep track of the maximum possible size.
- Iterate over the array using pointers i and j.
- Increment j until the difference between arr[j] and arr[i] is less than or equal to 5.
- Calculate the current size of the subarray, i.e., j – i + 1.
- If the current size is greater than the previous maximum size, update the maxLength to the current size.
- Increment i until the difference between arr[j] and arr[i] is greater than 5.
- Repeat steps 5-8 until j reaches the end of the array.
- Return maxLength.
Below is the implementation of the above approach:
C++
#include <iostream>#include <algorithm>using namespace std;int main() { int arr[] = {1, 10, 17, 12, 15, 2}; int n = sizeof(arr) / sizeof(arr[0]); sort(arr, arr + n); int i = 0, j = 0; int maxLength = 1; while (j < n) { if (arr[j] - arr[i] <= 5) { maxLength = max(maxLength, j - i + 1); j++; } else { i++; } } cout << maxLength << endl; return 0;}//This code is contributed by Tushar Rokade. |
Java
// java Code for the approachimport java.util.Arrays;class GFG { // Driver code public static void main(String[] args) { // Input array int[] arr = {1, 10, 17, 12, 15, 2}; // size of the array int n = arr.length; // sort the array Arrays.sort(arr); // two pointers i and j for traversal int i = 0, j = 0; int maxLength = 1; // traversing the array while (j < n) { // if difference is less or equal to 5 update // maxLength variable with count of elements // in between i and j pointers if (arr[j] - arr[i] <= 5) { maxLength = Math.max(maxLength, j - i + 1); j++; } // else increment i as differnece is greater // so to decrease it go to larger numbers else { i++; } } // print the result System.out.println(maxLength); }} |
Python3
# Python3 code for the approachif __name__ == '__main__': # Input array arr = [1, 10, 17, 12, 15, 2] n = len(arr) # Sort the array arr.sort() # two pointers i and j for traversal i = 0 j = 0 maxLength = 1 # traversing the array while j < n: # if difference is less or equal to 5 update # maxLength variable with count of elements # in between i and j pointers if arr[j] - arr[i] <= 5: maxLength = max(maxLength, j - i + 1) j += 1 # else increment i as differnece is greater # so to decrease it go to larger numbers else: i += 1 print(maxLength) |
C#
// C# code for the above approachusing System;using System.Linq;class GFG { static public void Main() { // Input array int[] arr = { 1, 10, 17, 12, 15, 2 }; // size of the array int n = arr.Length; // sort the array Array.Sort(arr); // two pointers i and j for traversal int i = 0, j = 0; int maxLength = 1; // traversing the array while (j < n) { // if difference is less or equal to 5 update // maxLength variable with count of elements // in between i and j pointers if (arr[j] - arr[i] <= 5) { maxLength = Math.Max(maxLength, j - i + 1); j++; } // else increment i as differnece is greater // so to decrease it go to larger numbers else { i++; } } // print the result Console.WriteLine(maxLength); }}// This code is contributed by Susobhan Akhuli |
Javascript
const arr = [1, 10, 17, 12, 15, 2];const n = arr.length;arr.sort((a, b) => a - b);let i = 0, j = 0;let maxLength = 1;while (j < n) { if (arr[j] - arr[i] <= 5) { maxLength = Math.max(maxLength, j - i + 1); j++; } else { i++; }}console.log(maxLength); |
Output
3
Time Complexity: O(nlog(n)).
Auxiliary Space: O(1).
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!
Share your thoughts in the comments
