Given an array A and positive integer K. The task is to find maximum number of elements for which the absolute difference of any of the pair does not exceed K.
Examples:
Input: A[] = {1, 26, 17, 12, 15, 2}, K = 5
Output: 3
There are maximum 3 values so that the absolute difference of each pair
does not exceed K(K=5) ie., {12, 15, 17}
Input: A[] = {1, 2, 5, 10, 8, 3}, K = 4
Output: 4
There are maximum 4 values so that the absolute difference of each pair
does not exceed K(K=4) ie., {1, 2, 3, 5}
Approach:
- Sort the given Array in ascending order.
- Iterate from index i = 0 to n.
- For every A[i] count how many values which are in range A[i] to A[i] + K
ie., A[i]<= A[j] <= A[i]+K - Return Max Count
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum elements// in which absolute difference of any pair// does not exceed Kint maxCount(int A[], int N, int K){ int maximum = 0; int i = 0, j = 0; // Sort the Given array sort(A, A + N); // Find max elements for (i = 0; i < N; i++) { // Count all elements which are in range // A[i] to A[i] + K while (j < N && A[j] <= A[i] + K){ j++; } maximum=max(maximum,j-i); } // Return the max count return maximum;}// Driver codeint main(){ int A[] = { 1, 26, 17, 12, 15, 2 }; int N = sizeof(A) / sizeof(A[0]); int K = 5; cout << maxCount(A, N, K); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG { // Function to return the maximum elements // in which absolute difference of any pair // does not exceed K static int maxCount(int A[], int N, int K) { int maximum = 0; int i = 0, j = 0; int start = 0; int end = 0; // Sort the Given array Arrays.sort(A); // Find max elements for (i = 0; i < N; i++) { // Count all elements which are in range // A[i] to A[i] + K while (j < N && A[j] <= A[i] + K) j++; if (maximum < (j - i)) { maximum = (j - i); start = i; end = j; } } // Return the max count return maximum; } // Driver code public static void main(String[] args){ int A[] = { 1, 26, 17, 12, 15, 2 }; int N = A.length; int K = 5; System.out.println(maxCount(A, N, K));}}// This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachdef maxCount(A, N, K): maximum = 0 start = 0 end = 0 j = 0 # Sort the Array A.sort() # Find max elements for i in range(0, N): while(j < N and A[j] <= A[i] + K): j += 1 if maximum < (j - i ): maximum = (j - i) start = i; end = j; # Return the maximum return maximum# Driver codeA = [1, 26, 17, 12, 15, 2] N = len(A)K = 5print(maxCount(A, N, K)) |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the maximum elements // in which absolute difference of any pair // does not exceed K static int maxCount(int []A, int N, int K) { int maximum = 0; int i = 0, j = 0; int start = 0; int end = 0; // Sort the Given array Array.Sort(A); // Find max elements for (i = 0; i < N; i++) { // Count all elements which are in range // A[i] to A[i] + K while (j < N && A[j] <= A[i] + K) j++; if (maximum < (j - i)) { maximum = (j - i); start = i; end = j; } } // Return the max count return maximum; } // Driver code public static void Main(){ int []A = { 1, 26, 17, 12, 15, 2 }; int N = A.Length; int K = 5; Console.Write(maxCount(A, N, K));}}/* This code contributed by PrinciRaj1992 */ |
PHP
<?php// PHP implementation of the above approach // Function to return the maximum // elements in which absolute difference // of any pair does not exceed K function maxCount($A, $N, $K) { $maximum = 0; $i = 0; $j = 0; $start = 0; $end = 0; // Sort the Given array sort($A); // Find max elements for ($i = 0; $i < $N; $i++) { // Count all elements which // are in range A[i] to A[i] + K while ($j < $N && $A[$j] <= $A[$i] + $K) $j++; if ($maximum < ($j - $i)) { $maximum = ($j - $i); $start = $i; $end = $j; } } // Return the max count return $maximum; } // Driver code $A = array( 1, 26, 17, 12, 15, 2 ); $N = Count($A); $K = 5; echo maxCount($A, $N, $K); // This code is contributed // by Arnab Kundu?> |
Javascript
<script>// JavaScript implementation of the above approach// Function to return the maximum elements// in which absolute difference of any pair// does not exceed Kfunction maxCount(A, N, K){ var maximum = 0; var i = 0, j = 0; var start = 0; var end = 0; // Sort the Given array A.sort((a,b)=> a-b) // Find max elements for (i = 0; i < N; i++) { // Count all elements which are in range // A[i] to A[i] + K while (j < N && A[j] <= A[i] + K) j++; if (maximum < (j - i)) { maximum = (j - i); start = i; end = j; } } // Return the max count return maximum;}// Driver codevar A = [1, 26, 17, 12, 15, 2 ];var N = A.length;var K = 5;document.write( maxCount(A, N, K));</script> |
Output:
3
Time Complexity: O(N logN), where N*logN is the time required to sort the given array
Auxiliary Space: O(1), no extra space required
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!
