Given an array arr[] and an integer K. The task is to find the size of the maximum sub-set such that every pair from the sub-set (X, Y) is of the form Y != (X * K) where X < Y.
Examples:
Input: arr[] = {2, 3, 6, 5, 4, 10}, K = 2
Output: 3
{2, 3, 5} is the required sub-setInput: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 2
Output: 6
Approach:
- Sort all the array elements.
- Create an empty set of integers S, which will hold the elements for the sub-set.
- Traverse the sorted array, and for each integer x in the array:
- If x % k = 0 or x / k is not already present in S then insert x into S.
- Else discard x and check the next element.
- Print the size of the set S in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the size of the required sub-setint sizeSubSet(int a[], int k, int n){ // Sort the array sort(a, a + n); // Set to store the contents of the required sub-set unordered_set<int> s; // Insert the elements satisfying the conditions for (int i = 0; i < n; i++) { if (a[i] % k != 0 || s.count(a[i] / k) == 0) s.insert(a[i]); } // Return the size of the set return s.size();}// Driver codeint main(){ int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int n = sizeof(a) / sizeof(a[0]); int k = 2; cout << sizeSubSet(a, k, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to return the size of the required sub-setstatic int sizeSubSet(int a[], int k, int n){ // Sort the array Arrays.sort(a); // HashMap to store the contents // of the required sub-set HashMap< Integer, Integer> s = new HashMap< Integer, Integer>(); // Insert the elements satisfying the conditions for (int i = 0; i < n; i++) { if (a[i] % k != 0 || s.get(a[i] / k) == null) s.put(a[i], s.get(a[i]) == null ? 1 : s.get(a[i]) + 1); } // Return the size of the set return s.size();}// Driver codepublic static void main(String args[]){ int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int n = a.length; int k = 2; System.out.println( sizeSubSet(a, k, n));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachimport math as mt # Function to return the size of the required sub-setdef sizeSubSet(a, k, n): # Sort the array a.sort() # Set to store the contents of the required sub-set s=set() # Insert the elements satisfying the conditions for i in range(n): if (a[i] % k != 0 or a[i] // k not in s): s.add(a[i]) # Return the size of the set return len(s) # Driver codea=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]n = len(a)k = 2print(sizeSubSet(a, k, n))# This is contributed by Mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to return the size of // the required sub-setstatic int sizeSubSet(int []a, int k, int n){ // Sort the array Array.Sort(a); // HashMap to store the contents // of the required sub-set Dictionary<int, int> s = new Dictionary<int, int>(); // Insert the elements satisfying the conditions for (int i = 0; i < n; i++) { if (a[i] % k != 0 || !s.ContainsKey(a[i] / k)) { if(s.ContainsKey(a[i])) { var val = s[a[i]]; s.Remove(a[i]); s.Add(a[i], val + 1); } else { s.Add(a[i], 1); } } } // Return the size of the set return s.Count;}// Driver codepublic static void Main(String []args){ int []a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int n = a.Length; int k = 2; Console.WriteLine(sizeSubSet(a, k, n));}}// This code is contributed by PrinciRaj1992 |
PHP
<?php// Php implementation of the approach // Function to return the size of// the required sub-set function sizeSubSet($a, $k, $n){ // Sort the array sort($a) ; // Set to store the contents of // the required sub-set $s = array(); // Insert the elements satisfying // the conditions for ($i = 0 ; $i < $n ; $i++) { if ($a[$i] % $k != 0 or !in_array(floor($a[$i] / $k), $s)) array_push($s, $a[$i]); } // Return the size of the set return sizeof($s);}// Driver code $a = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10 );$n = sizeof($a);$k = 2;echo sizeSubSet($a, $k, $n);// This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the size of the// required sub-setfunction sizeSubSet(a, k, n){ // Sort the array a.sort(function(a, b){return a - b;}); // HashMap to store the contents // of the required sub-set let s = new Map(); // Insert the elements satisfying the conditions for(let i = 0; i < n; i++) { if (a[i] % k != 0 || s.get(a[i] / k) == null) s.set(a[i], s.get(a[i]) == null ? 1 : s.get(a[i]) + 1); } // Return the size of the set return s.size;}// Driver codelet a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];let n = a.length;let k = 2;document.write(sizeSubSet(a, k, n));// This code is contributed by patel2127</script> |
Output:
6
Time Complexity: O(n*log(n)), As we are sorting the array
Auxiliary Space: 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!
