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-set int 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 code int 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 approach import java.util.*; class GFG { // Function to return the size of the required sub-set static 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 code public 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 approach import math as mt # Function to return the size of the required sub-set def 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 code a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] n = len (a) k = 2 print (sizeSubSet(a, k, n)) # This is contributed by Mohit kumar 29 |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the size of // the required sub-set static 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 code public 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-set function 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 code let 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> |
6
Time Complexity: O(n*log(n)), As we are sorting the array
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!