Given an array arr[] and a positive integer K, the task is to find the maximum count of disjoint pairs (arr[i], arr[j]) such that arr[j] ? K * arr[i].
Examples:
Input: arr[] = { 1, 9, 4, 7, 3 }, K = 2
Output: 2
Explanation:
There can be 2 possible pairs that can formed from the given array i.e., (4, 1) and (7, 3) that satisfy the given conditions.Input: arr[] = {2, 3, 4, 5, 6, 7, 8, 9}, K = 3
Output: 2
Approach: The given problem can be solved by using the Two Pointer Approach. Follow the steps below to solve the given problem:
- Sort the given array in increasing order.
- Initialize two variables i and j as 0 and (N / 2) respectively and variable count that stores the resultant maximum count of pairs.
- Traverse the given array over the range [0, N/2] and perform the following steps:
- Increment the value of j until j < N and arr[j] < K * arr[i].
- If the value of j is less than N, then increment the count of pairs by 1.
- Increment the value of j by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum count// of disjoint pairs such that arr[i]// is at least K*arr[j]int maximizePairs(int arr[], int n, int k){ // Sort the array sort(arr, arr + n); // Initialize the two pointers int i = 0, j = n / 2; // Stores the total count of pairs int count = 0; for (i = 0; i < n / 2; i++) { // Increment j until a valid // pair is found or end of the // array is reached while (j < n && (k * arr[i]) > arr[j]) j++; // If j is not the end of the // array, then a valid pair if (j < n) count++; j++; } // Return the possible count return count;}// Driver Codeint main(){ int arr[] = { 1, 9, 4, 7, 3 }; int N = sizeof(arr) / sizeof(int); int K = 2; cout << maximizePairs(arr, N, K); return 0;} |
Java
// Java code for above approachimport java.util.*;class GFG{// Function to find the maximum count// of disjoint pairs such that arr[i]// is at least K*arr[j]static int maximizePairs(int arr[], int n, int k){ // Sort the array Arrays.sort(arr); // Initialize the two pointers int i = 0, j = n / 2; // Stores the total count of pairs int count = 0; for (i = 0; i < n / 2; i++) { // Increment j until a valid // pair is found or end of the // array is reached while (j < n && (k * arr[i]) > arr[j]) j++; // If j is not the end of the // array, then a valid pair if (j < n) count++; j++; } // Return the possible count return count;}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 9, 4, 7, 3 }; int N = arr.length; int K = 2; System.out.print(maximizePairs(arr, N, K));}}// This code is contributed by avijitmondal1998. |
Python3
# Python 3 program for the above approach# Function to find the maximum count# of disjoint pairs such that arr[i]# is at least K*arr[j]def maximizePairs(arr, n, k): # Sort the array arr.sort() # Initialize the two pointers i = 0 j = n // 2 # Stores the total count of pairs count = 0 for i in range(n//2): # Increment j until a valid # pair is found or end of the # array is reached while (j < n and (k * arr[i]) > arr[j]): j += 1 # If j is not the end of the # array, then a valid pair if (j < n): count += 1 j += 1 # Return the possible count return count# Driver Codeif __name__ == '__main__': arr = [1, 9, 4, 7, 3] N = len(arr) K = 2 print(maximizePairs(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# code for above approachusing System;class GFG{// Function to find the maximum count// of disjoint pairs such that arr[i]// is at least K*arr[j]static int maximizePairs(int []arr, int n, int k){ // Sort the array Array.Sort(arr); // Initialize the two pointers int i = 0, j = n / 2; // Stores the total count of pairs int count = 0; for (i = 0; i < n / 2; i++) { // Increment j until a valid // pair is found or end of the // array is reached while (j < n && (k * arr[i]) > arr[j]) j++; // If j is not the end of the // array, then a valid pair if (j < n) count++; j++; } // Return the possible count return count;}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 9, 4, 7, 3 }; int N = arr.Length; int K = 2; Console.Write(maximizePairs(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum count// of disjoint pairs such that arr[i]// is at least K*arr[j]function maximizePairs(arr, n, k) { // Sort the array arr.sort((a, b) => a - b); // Initialize the two pointers let i = 0, j = Math.floor(n / 2); // Stores the total count of pairs let count = 0; for (i = 0; i < Math.floor(n / 2); i++) { // Increment j until a valid // pair is found or end of the // array is reached while (j < n && k * arr[i] > arr[j]) j++; // If j is not the end of the // array, then a valid pair if (j < n) count++; j++; } // Return the possible count return count;}// Driver Codelet arr = [1, 9, 4, 7, 3];let N = arr.length;let K = 2;document.write(maximizePairs(arr, N, K));// This code is contributed by gfgking.</script> |
Output:
2
Time Complexity: O(N*log 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!