Given an array arr[] and an integer K, find the maximum number of pairs that can be made such that one element is K times the other i.e, arr[i]=K*arr[j].
Examples:
Input: arr[] = {1, 2, 1, 2, 4} K = 2
Output: 2
Explanation: There are two possible ways to construct pairs: ({1, 2}, {1, 2}) and ({1, 2}, {2, 4}).Input: a = {5, 4, 3, 2, 1} K = 2
Output: 1
Explanation: We can construct either set {1, 2} or set {2, 4}.
Approach: Sort the given array arr[] and check all the possible pairs of the array arr[] and check if a given (i, j) arr[i]=2*arr[j]. Follow the steps below to solve the problem:
- Sort the array arr[] using the sort function in C++ STL.
- Initialize a vector used to keep the count of already used elements.
- Initialize the variable ans as 0 to store the count of all possible pairs.
- Iterate over the range [0, N-1] using the variable i and perform the following steps:
- Iterate over the range [l, N-1] using the variable j and do the following:
- If the value of used[j] and used[i] are false and arr[j]=K*arr[i], then, set the value of used[i] and used[j] to true and increase the value of ans by 1 and break the loop.
- Iterate over the range [l, N-1] using the variable j and do the following:
- Finally, after completing the above steps, print the value of ans.
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 number// of pairs.int maxPairs(vector<int> a, int k){ // Sort the array. sort(a.begin(), a.end()); int n = a.size(), ans = 0; // mark as used vector<bool> used(n); // iterate over all elements for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // if condition is satisfied, // pair the elements if (!used[j] && a[j] == k * a[i] && !used[i]) { used[j] = used[i] = true; ans++; break; } } } return ans;}// Driver Codeint32_t main(){ vector<int> a{ 1, 2, 1, 2, 4 }; int k = 2; cout << maxPairs(a, k); return 0;} |
Java
// Java program for the above approach.import java.util.Arrays;class GFG { // Function to find the maximum number // of pairs.public static int maxPairs(int[] a, int k){ // Sort the array. Arrays.sort(a); int n = a.length, ans = 0; // mark as used boolean[] used = new boolean[n]; // iterate over all elements for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // if condition is satisfied, // pair the elements if (!used[j] && a[j] == k * a[i] && !used[i]) { used[i] = true; used[j] = used[i]; ans++; break; } } } return ans;} // Driver Code public static void main(String args[]) { int[] a = {1, 2, 1, 2, 4}; int k = 2; System.out.println(maxPairs(a, k)); }}// This code is contributed by _saurabh_jaiswal. |
Python3
# Python Program for the above approach# Function to find the maximum number# of pairs.def maxPairs(a, k): # Sort the array. a.sort() n = len(a) ans = 0 # mark as used used = [False] * n # iterate over all elements for i in range(0, n): for j in range(i + 1, n): # if condition is satisfied, # pair the elements if (used[j] == False and a[j] == k * a[i] and used[i] == False): used[j] = used[j] = True ans += 1 break return ans# Driver Codea = [1, 2, 1, 2, 4]k = 2print(maxPairs(a, k))# This code is contributed by _saurabh_jaiswal |
C#
// C# program for the above approach.using System;using System.Collections.Generic;class GFG{// Function to find the maximum number// of pairs.static int maxPairs(List<int> a, int k){ // Sort the array. a.Sort(); int n = a.Count, ans = 0; // mark as used int [] Ar = new int[n]; List<int> used = new List<int>(Ar); // iterate over all elements for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // if condition is satisfied, // pair the elements if (used[j]==0 && a[j] == k * a[i] && used[i]==0) { used[j] = used[i] = 1; ans++; break; } } } return ans;}// Driver Code public static void Main(){ List<int> a = new List<int>(){ 1, 2, 1, 2, 4 }; int k = 2; Console.Write(maxPairs(a, k)); }}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program for the above approach // Function to find the maximum number // of pairs. function maxPairs(a, k) { // Sort the array. a.sort(function (x, y) { return x - y }); let n = a.length, ans = 0; // mark as used let used = new Array(n).fill(false); // iterate over all elements for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // if condition is satisfied, // pair the elements if (used[j] == false && a[j] == k * a[i] && used[i] == false) { used[j] = used[j] = true; ans++; break; } } } return ans; } // Driver Code let a = [1, 2, 1, 2, 4]; let k = 2; document.write(maxPairs(a, k)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N^2)
Space Complexity: O(N)
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
