Given two arrays A[] and B[] and an integer K, the task is to maximize the count of integers of array B[] that can be made equal with array A[] by adding or subtracting any integer in the range [0, K].
Examples:
Input: K=5, A[] = [100, 65, 35, 85, 55], B[] = [30, 60, 75, 95]
Output: 3
Explanation:
30 + 5, 60 + 5, 95 + 5 gives the values which are equal with few elements of array A[].Input: K = 5, A[] = [10, 20, 30, 40, 50], B[] = [1, 20, 3]
Output: 1
Explanation:
Only the 2nd value can be made equal, Since its value [20] can be changed to [20] by adding/subtracting 0 from it.
Approach: The idea is to check whether the absolute difference between elements of the array B[] with any element of the array A[] is less than or equals to K. If yes then include this in the count. Print the count all such elements after checking the above condition for all the elements in the array B[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that count the number of// integers from array B[] such that// subtracting element in the range// [0, K] given any element in A[]void countElement(int A[], int N, int B[], int M, int K){ // To store the count of element int cnt = 0; // Traverse the array B[] for (int i = 0; i < M; i++) { int currentElement = B[i]; // Traverse the array A[] for (int j = 0; j < N; j++) { // Find the difference int diff = abs(currentElement - A[j]); // If difference is atmost // K then increment the cnt if (diff <= K) { cnt++; break; } } } // Print the count cout << cnt;}// Driver Codeint main(){ // Given array A[] and B[] int A[] = { 100, 65, 35, 85, 55 }; int B[] = { 30, 60, 75, 95 }; // Given K int K = 5; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); // Function Call countElement(A, N, B, M, K); return 0;} |
Java
// Java program for the above approachclass GFG{// Function that count the number of// integers from array B[] such that// subtracting element in the range// [0, K] given any element in A[]static void countElement(int A[], int N, int B[], int M, int K){ // To store the count of element int cnt = 0; // Traverse the array B[] for(int i = 0; i < M; i++) { int currentElement = B[i]; // Traverse the array A[] for(int j = 0; j < N; j++) { // Find the difference int diff = Math.abs( currentElement - A[j]); // If difference is atmost // K then increment the cnt if (diff <= K) { cnt++; break; } } } // Print the count System.out.print(cnt);}// Driver Codepublic static void main(String[] args){ // Given array A[] and B[] int A[] = { 100, 65, 35, 85, 55 }; int B[] = { 30, 60, 75, 95 }; // Given K int K = 5; int N = A.length; int M = B.length; // Function call countElement(A, N, B, M, K);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approach# Function that count the number of# integers from array B such that# subtracting element in the range# [0, K] given any element in Adef countElement(A, N, B, M, K): # To store the count of element cnt = 0 # Traverse the array B for i in range(M): currentElement = B[i] # Traverse the array A for j in range(N): # Find the difference diff = abs(currentElement - A[j]) # If difference is atmost # K then increment the cnt if(diff <= K): cnt += 1 break # Print the count print(cnt)# Driver Codeif __name__ == '__main__': # Given array A and B A = [ 100, 65, 35, 85, 55 ] B = [ 30, 60, 75, 95 ] N = len(A) M = len(B) # Given K K = 5 # Function call countElement(A, N, B, M, K)# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{// Function that count the number of// integers from array []B such that// subtracting element in the range// [0, K] given any element in []Astatic void countElement(int []A, int N, int []B, int M, int K){ // To store the count of element int cnt = 0; // Traverse the array []B for(int i = 0; i < M; i++) { int currentElement = B[i]; // Traverse the array []A for(int j = 0; j < N; j++) { // Find the difference int diff = Math.Abs( currentElement - A[j]); // If difference is atmost // K then increment the cnt if (diff <= K) { cnt++; break; } } } // Print the count Console.Write(cnt);}// Driver Codepublic static void Main(String[] args){ // Given array []A and []B int []A = { 100, 65, 35, 85, 55 }; int []B = { 30, 60, 75, 95 }; // Given K int K = 5; int N = A.Length; int M = B.Length; // Function call countElement(A, N, B, M, K);}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript Script program to implement// the above approach// Function that count the number of// integers from array B[] such that// subtracting element in the range// [0, K] given any element in A[]function countElement(A, N, B, M, K){ // To store the count of element let cnt = 0; // Traverse the array B[] for(let i = 0; i < M; i++) { let currentElement = B[i]; // Traverse the array A[] for(let j = 0; j < N; j++) { // Find the difference let diff = Math.abs( currentElement - A[j]); // If difference is atmost // K then increment the cnt if (diff <= K) { cnt++; break; } } } // Print the count document.write(cnt);}// Driver Code // Given array A[] and B[] let A = [ 100, 65, 35, 85, 55 ]; let B = [ 30, 60, 75, 95 ]; // Given K let K = 5; let N = A.length; let M = B.length; // Function call countElement(A, N, B, M, K); </script> |
Output:
3
Time Complexity: O(N*M), where N and M are the lengths of the arrays A[] and B[].
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
