Given two arrays A[] of size N and B[] of size M and an integer K, the task is to select at most one element from array B[] for every element A[i] such that the element lies in the range [A[i] – K, A[i] + K] ( for 0 <= i <= N – 1 ). Print the maximum number of elements that can be selected from the array B[].
Examples:
Input: N = 4, A[] = {60, 45, 80, 60}, M = 3, B[] = {30, 60, 75}, K= 5
Output: 2
Explanation :
B[0] (= 30): Not present in any of the ranges [A[i] + K, A[i] – K].
B[1] (= 60): B[1] lies in the range [A[0] – K, A[0] + K], i.e. [55, 65].
B[2] (= 75): B[2] lies in the range [A[2] – K, A[2] + K], i.e. [75, 85].Input: N = 3 A[] = {10, 20, 30}, M = 3, B[] = {5, 10, 15}, K = 10
Output: 2
Naive Approach: The simplest approach to solve the problem is to traverse the array A[], search linearly in the array B[] and mark visited if the value of the array B[] is selected. Finally, print the maximum number of elements from the array B[] that can be selected.
Time Complexity: O(N * M)
Auxiliary Space: O(M)
Efficient Approach: Sort both the arrays A[] and B[] and try to assign the element of B[] that is in a range [A[i] – K, A[i] + K]. Follow the steps below to solve the problem:
- Sort the arrays A[] and B[].
- Initialize a variable, say j as 0, to keep track in the array B[] and count as 0 to store the answer.
- Iterate in a range [0, N – 1] and perform the following steps:
- Iterate in a while loop till j < M and B[j]< A[i] – K, then increase the value of j by 1.
- If the value of j is less than M and B[j] is greater than equal to A[i] – K and B[j] is less than equal to A[i] + K then increase the value of count and j by 1.
- After completing the above steps, print the value of count as the final value of 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 count the maximum number of// elements that can be selected from array// B[] lying in the range [A[i] - K, A[i] + K]int selectMaximumEle(int n, int m, int k, int A[], int B[]){ // Sort both arrays sort(A, A + n); sort(B, B + m); int j = 0, count = 0; // Iterate in the range[0, N-1] for (int i = 0; i < n; i++) { // Increase the value of j till // B[j] is smaller than A[i] while (j < m && B[j] < A[i] - k) { j++; } // Increasing count variable when B[j] // lies in the range [A[i]-K, A[i]+K] if (j < m && B[j] >= A[i] - k && B[j] <= A[i] + k) { count++; j++; } } // Finally, return the answer return count;}// Driver Codeint main(){ // Given Input int N = 3, M = 3, K = 10; int A[] = { 10, 20, 30 }; int B[] = { 5, 10, 15 }; // Function Call cout << selectMaximumEle(N, M, K, A, B) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.Arrays;class GFG{ // Function to count the maximum number of // elements that can be selected from array // B[] lying in the range [A[i] - K, A[i] + K] static int selectMaximumEle(int n, int m, int k, int A[], int B[]) { // Sort both arrays Arrays.sort(A); Arrays.sort(B); int j = 0, count = 0; // Iterate in the range[0, N-1] for (int i = 0; i < n; i++) { // Increase the value of j till // B[j] is smaller than A[i] while (j < m && B[j] < A[i] - k) { j++; } // Increasing count variable when B[j] // lies in the range [A[i]-K, A[i]+K] if (j < m && B[j] >= A[i] - k && B[j] <= A[i] + k) { count++; j++; } } // Finally, return the answer return count; } // Driver Code public static void main(String[] args) { // Given Input int N = 3, M = 3, K = 10; int A[] = { 10, 20, 30 }; int B[] = { 5, 10, 15 }; // Function Call System.out.println(selectMaximumEle(N, M, K, A, B)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach# Function to count the maximum number of# elements that can be selected from array# B[] lying in the range [A[i] - K, A[i] + K]def selectMaximumEle(n, m, k, A, B): # Sort both arrays A.sort() B.sort() j = 0 count = 0 # Iterate in the range[0, N-1] for i in range(n): # Increase the value of j till # B[j] is smaller than A[i] while (j < m and B[j] < A[i] - k): j += 1 # Increasing count variable when B[j] # lies in the range [A[i]-K, A[i]+K] if (j < m and B[j] >= A[i] - k and B[j] <= A[i] + k): count += 1 j += 1 # Finally, return the answer return count# Driver Code# Given InputN = 3M = 3K = 10A = [ 10, 20, 30 ]B = [ 5, 10, 15 ]# Function Callprint(selectMaximumEle(N, M, K, A, B))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the maximum number of// elements that can be selected from array// B[] lying in the range [A[i] - K, A[i] + K]static int selectMaximumEle(int n, int m, int k, int[] A, int[] B){ // Sort both arrays Array.Sort(A); Array.Sort(B); int j = 0, count = 0; // Iterate in the range[0, N-1] for(int i = 0; i < n; i++) { // Increase the value of j till // B[j] is smaller than A[i] while (j < m && B[j] < A[i] - k) { j++; } // Increasing count variable when B[j] // lies in the range [A[i]-K, A[i]+K] if (j < m && B[j] >= A[i] - k && B[j] <= A[i] + k) { count++; j++; } } // Finally, return the answer return count;}// Driver codepublic static void Main(){ // Given Input int N = 3, M = 3, K = 10; int[] A = { 10, 20, 30 }; int[] B = { 5, 10, 15 }; // Function Call Console.WriteLine(selectMaximumEle(N, M, K, A, B));}}// This code is contributed by avijitmondal1998 |
Javascript
<script> // Javascript program for the above approach// Function to count the maximum number of// elements that can be selected from array// B[] lying in the range [A[i] - K, A[i] + K]function selectMaximumEle(n, m, k, A, B) { // Sort both arrays A.sort((a, b) => a - b); B.sort((a, b) => a - b); let j = 0, count = 0; // Iterate in the range[0, N-1] for (let i = 0; i < n; i++) { // Increase the value of j till // B[j] is smaller than A[i] while (j < m && B[j] < A[i] - k) { j++; } // Increasing count variable when B[j] // lies in the range [A[i]-K, A[i]+K] if (j < m && B[j] >= A[i] - k && B[j] <= A[i] + k) { count++; j++; } } // Finally, return the answer return count;}// Driver Code// Given Inputlet N = 3, M = 3, K = 10;let A = [10, 20, 30];let B = [5, 10, 15];// Function Calldocument.write(selectMaximumEle(N, M, K, A, B) + "<br>");// This code is contributed by _saurabh_jaiswal.</script> |
Output:
2
Time Complexity: O(N*log(N)+M*log(M))
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!
