Given an array arr[] of size N, the task is to find the minimum number of operations to reduce the array by deleting an element and all its multiples from the array in one operation.
Examples:
Input: N = 5, arr[] = {5, 2, 3, 8, 7}
Output: 4
Explanation: Removing 2, will make it remove 8 (as it is a multiple of 2),
then 3, 5, 7 would be removed in one operation each,
Thus, total count = 1 + 3 = 4 (Required Answer)Input: N = 7, arr[] = {12, 10, 2, 3, 5, 6, 27}
Output: 3
Explanation: Removing 2 and its multiples 10, 12, 6 in one operation. So count = 1.
Then, remove 3 and 27 (multiple of 3) in one operation. So total count = 1+1 = 2.
Last element left would be 5 which will again take one operation.
Thus, total count = 2 + 1 = 3 (Required Answer)
Approach: The approach to the solution is based on the following idea:
Sort the array and then start iterating from the start.
For each element group all its multiples together if it already is not part of any group.
The total number of group is the required answer.
Follow the steps to solve the problem:
- Sort the array in increasing order.
- Iterate from the i = 0 to N-1 and:
- If this element is part of any group or not.
- If not then group this element and all its multiples together.
- Otherwise, skip this and continue iteration.
- Return the count of the total number of groups.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to do required operationvoid solve(int n, vector<int>& v){ int M = INT_MIN; for (int i = 0; i < n; i++) M = max(M, v[i]); // Initializing a visited array // of max size of N and marking // each element as 0(false) vector<int> vis(M + 1, 0); // Sorting the given array // such that each element // appear in increasing order sort(v.begin(), v.end()); // Special case for 1 for (int i = 0; i < v.size(); i++) { if (v[i] == 1) { cout << 1 << "\n"; return; } } // Initializing final count answer int count = 0; // Traverse in the given array for (int i = 0; i < v.size(); i++) { // Check if element is // not visited yet if (vis[v[i]] == 0) { // Mark it as visited vis[v[i]] = 1; // Store that element for // further traversing through // its multiples int temp = v[i]; // Then, traverse from N // min to max range and // mark all the multiples of // stored element as visited for (int i = 1; i <= M; i++) { if (i * temp <= M) { vis[i * temp] = 1; } } // Increase count by 1 for // each iteration count++; } } // Print the final count answer cout << count << "\n";}// Driver Codeint main(){ // Taking input int N = 5; vector<int> arr = { 5, 2, 3, 8, 7 }; // Function call solve(N, arr); return 0;} |
Java
// Java code for the above approachimport java.util.*;public class GFG { // Function to do required operation static void solve(int n, int[] v) { int M = Integer.MIN_VALUE; for (int i = 0; i < n; i++) M = Math.max(M, v[i]); // Initializing a visited array // of max size of N and marking // each element as 0(false) int[] vis = new int[M + 1]; for (int i = 0; i < M + 1; i++) { vis[i] = 0; } // Sorting the given array // such that each element // appear in increasing order Arrays.sort(v); // Special case for 1 for (int i = 0; i < v.length; i++) { if (v[i] == 1) { System.out.println(1); return; } } // Initializing final count answer int count = 0; // Traverse in the given array for (int i = 0; i < v.length; i++) { // Check if element is // not visited yet if (vis[v[i]] == 0) { // Mark it as visited vis[v[i]] = 1; // Store that element for // further traversing through // its multiples int temp = v[i]; // Then, traverse from N // min to max range and // mark all the multiples of // stored element as visited for (int j = 1; j <= M; j++) { if (j * temp <= M) { vis[j * temp] = 1; } } // Increase count by 1 for // each iteration count++; } } // Print the final count answer System.out.println(count); } // Driver Code public static void main(String args[]) { // Taking input int N = 5; int[] arr = { 5, 2, 3, 8, 7 }; // Function call solve(N, arr); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 code for the above approachINT_MIN = -2147483647 - 1# Function to do required operationdef solve(n, v): M = INT_MIN for i in range(n): M = max(M, v[i]) # Initializing a visited array # of max size of N and marking # each element as 0(false) vis = [0]*(M+1) # Sorting the given array # such that each element # appear in increasing order v.sort() # Special case for 1 for i in range(len(v)): if (v[i] == 1): print(1) return # Initializing final count answer count = 0 # Traverse in the given array for i in range(len(v)): # Check if element is # not visited yet if (vis[v[i]] == 0): # Mark it as visited vis[v[i]] = 1 # Store that element for # further traversing through # its multiples temp = v[i] # Then, traverse from N # min to max range and # mark all the multiples of # stored element as visited for i in range(1,M+1): if (i * temp <= M): vis[i * temp] = 1 # Increase count by 1 for # each iteration count += 1 # Print the final count answer print(count)# Driver Code# Taking inputN = 5arr = [5, 2, 3, 8, 7]# Function callsolve(N, arr)# This code is contributed by shinjanpatra |
C#
// C# code for the above approachusing System;class GFG { // Function to do required operation static void solve(int n, int[] v) { int M = Int32.MinValue; for (int i = 0; i < n; i++) M = Math.Max(M, v[i]); // Initializing a visited array // of max size of N and marking // each element as 0(false) int[] vis = new int[M + 1]; for (int i = 0; i < M + 1; i++) { vis[i] = 0; } // Sorting the given array // such that each element // appear in increasing order Array.Sort(v); // Special case for 1 for (int i = 0; i < v.Length; i++) { if (v[i] == 1) { Console.WriteLine(1); return; } } // Initializing final count answer int count = 0; // Traverse in the given array for (int i = 0; i < v.Length; i++) { // Check if element is // not visited yet if (vis[v[i]] == 0) { // Mark it as visited vis[v[i]] = 1; // Store that element for // further traversing through // its multiples int temp = v[i]; // Then, traverse from N // min to max range and // mark all the multiples of // stored element as visited for (int j = 1; j <= M; j++) { if (j * temp <= M) { vis[j * temp] = 1; } } // Increase count by 1 for // each iteration count++; } } // Print the final count answer Console.WriteLine(count); } // Driver Code public static void Main() { // Taking input int N = 5; int[] arr = { 5, 2, 3, 8, 7 }; // Function call solve(N, arr); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach const INT_MIN = -2147483647 - 1; // Function to do required operation const solve = (n, v) => { let M = INT_MIN; for (let i = 0; i < n; i++) M = Math.max(M, v[i]); // Initializing a visited array // of max size of N and marking // each element as 0(false) let vis = new Array(M + 1).fill(0); // Sorting the given array // such that each element // appear in increasing order v.sort(); // Special case for 1 for (let i = 0; i < v.length; i++) { if (v[i] == 1) { document.write("1<br/>"); return; } } // Initializing final count answer let count = 0; // Traverse in the given array for (let i = 0; i < v.length; i++) { // Check if element is // not visited yet if (vis[v[i]] == 0) { // Mark it as visited vis[v[i]] = 1; // Store that element for // further traversing through // its multiples let temp = v[i]; // Then, traverse from N // min to max range and // mark all the multiples of // stored element as visited for (let i = 1; i <= M; i++) { if (i * temp <= M) { vis[i * temp] = 1; } } // Increase count by 1 for // each iteration count++; } } // Print the final count answer document.write(`${count}<br/>`); } // Driver Code // Taking input let N = 5; let arr = [5, 2, 3, 8, 7]; // Function call solve(N, arr);// This code is contributed by rakeshsahni</script> |
Output
4
Time Complexity: O(N*M) where M is the maximum element of the array
Auxiliary Space: O(M)
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!
