Minimum number of operations required to delete all elements of the array

0 0 7 minutes read

Given an integer array arr, the task is to print the minimum number of operations required to delete all elements of the array.
In an operation, any element from the array can be chosen at random and every element divisible by it can be removed from the array.

Examples:

Input: arr[] = {2, 4, 6, 3, 5, 10}
Output: 3
Choosing 2 as the first element will remove 2, 4, 6 and 10 from the array.
Now choose 3 which will result in the removal of 3.
Finally, the only element left to choose is 5.

Input: arr[] = {2, 5, 3, 7, 11}
Output: 5

Approach: For optimal results, the smallest element from the array should be chosen from the remaining elements one after another until all the elements of the array are deleted.

Sort the array in ascending order and find the multiple of element in complete vector.
For each element which are divisible by choose element mark it 0, and decrease the value of N.
Return the value of N.

Below is the implementation of the above approach.

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
int solve(int N, vector<int> A)
{
    sort(A.begin(), A.end());
    int a = 0;
    for (int i = 0; i < A.size() - 1; i++) {
        int c = 0;
        if (A[i] != 0) {
            for (int j = i + 1; j < A.size(); j++) {
                if (A[j] % A[i] == 0 && A[j] != 0
                    && A[i] != 0) {
                    A[j] = 0;
                    N--;
                }
            }
        }
    }
    if (N == 0) {
        N = 1;
    }
    return N;
}
// Driver program
int main()
{
    vector<int> v = { 4, 6, 2, 8, 7, 21, 24, 49, 44 };
    int n = v.size();
 
    cout << solve(n, v);
    return 0;
}
// This code is contributed by Raunak_Kumar

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Java implementation of the above approach
 
  static int solve(int N, int[] A)
  {
    Arrays.sort(A);
    int a = 0;
    for (int i = 0; i < A.length - 1; i++) {
      int c = 0;
      if (A[i] != 0) {
        for (int j = i + 1; j < A.length; j++) {
          if (A[j] % A[i] == 0 && A[j] != 0
              && A[i] != 0) {
            A[j] = 0;
            N--;
          }
        }
      }
    }
    if (N == 0) {
      N = 1;
    }
    return N;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[] v = { 4, 6, 2, 8, 7, 21, 24, 49, 44 };
    int n = v.length;
 
    System.out.println(solve(n, v));
  }
}
 
// This code is contributed by shinjanpatra

Python3

# Python implementation of the above approach
def solve(N,A):
    A.sort()
    a = 0
    for i in range(len(A) - 1):
        c = 0
        if (A[i] != 0):
            for j in range(i + 1,len(A)):
                if (A[j] % A[i] == 0 and A[j] != 0 and A[i] != 0):
                    A[j] = 0
                    N -= 1
    if (N == 0):
        N = 1
    return N
 
# Driver program
v = [ 4, 6, 2, 8, 7, 21, 24, 49, 44 ]
n = len(v)
 
print(solve(n, v))
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
class GFG {
 
  static int solve(int N, int[] A)
  {
    Array.Sort(A);
//    int a = 0;
    for (int i = 0; i < A.Length - 1; i++) {
//      int c = 0;
      if (A[i] != 0) {
        for (int j = i + 1; j < A.Length; j++) {
          if (A[j] % A[i] == 0 && A[j] != 0
              && A[i] != 0) {
            A[j] = 0;
            N--;
          }
        }
      }
    }
    if (N == 0) {
      N = 1;
    }
    return N;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int[] v = { 4, 6, 2, 8, 7, 21, 24, 49, 44 };
    int n = v.Length;
 
    Console.WriteLine(solve(n, v));
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
 
// JavaScript implementation of the above approach
let n = -1;
 
function solve(A)
{
    A.sort((a,b)=> a - b);
    let a = 0;
    for (let i = 0; i < A.length - 1; i++) {
        let c = 0;
        if (A[i] != 0) {
            for (let j = i + 1; j < A.length; j++) {
                if (A[j] % A[i] == 0 && A[j] != 0 && A[i] != 0) {
                    A[j] = 0;
                    n--;
                }
            }
        }
    }
    if (n == 0) {
        n = 1;
    }
    return n;
}
 
// Driver program
let v = [ 4, 6, 2, 8, 7, 21, 24, 49, 44 ];
n = v.length;
 
document.write(solve(v));
 
// This code is contributed by shinjanpatra
 
</script>

Output

Time Complexity: O(N² logN), where N is the size of the array
Space Complexity: O(1)

Approach: For optimal results, the smallest element from the array should be chosen from the remaining elements one after another until all the elements of the array are deleted.

Sort the array in ascending order and prepare a hash for occurrences.
For each unmarked element starting from beginning mark all elements which are divisible by choose element, and increase the result counter.

Below is the implementation of the above approach

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
#define MAX 10000
 
using namespace std;
 
int hashTable[MAX];
 
// function to find minimum operations
int minOperations(int arr[], int n)
{
    // sort array
    sort(arr, arr + n);
 
    // prepare hash of array
    for (int i = 0; i < n; i++)
        hashTable[arr[i]]++;
 
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (hashTable[arr[i]]) {
            for (int j = i; j < n; j++)
                if (arr[j] % arr[i] == 0)
                    hashTable[arr[j]] = 0;
            res++;
        }
    }
 
    return res;
}
 
// Driver program
int main()
{
    int arr[] = { 4, 6, 2, 8, 7, 21, 24, 49, 44 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << minOperations(arr, n);
    return 0;
}

Java

//Java implementation of the above approach 
import java.util.*;
class Solution
{
static final int MAX=10000; 
 
static int hashTable[]= new int[MAX]; 
 
// function to find minimum operations 
static int minOperations(int arr[], int n) 
{ 
    // sort array 
    Arrays.sort(arr); 
 
    // prepare hash of array 
    for (int i = 0; i < n; i++) 
        hashTable[arr[i]]++; 
 
    int res = 0; 
    for (int i = 0; i < n; i++) { 
        if (hashTable[arr[i]]!=0) { 
            for (int j = i; j < n; j++) 
                if (arr[j] % arr[i] == 0) 
                    hashTable[arr[j]] = 0; 
            res++; 
        } 
    } 
 
    return res; 
} 
 
// Driver program 
public static void main(String args[]) 
{ 
    int arr[] = { 4, 6, 2, 8, 7, 21, 24, 49, 44 }; 
    int n = arr.length; 
 
    System.out.print( minOperations(arr, n)); 
  
} 
}
// This code is contributed by Arnab Kundu

Python 3

# Python 3 implementation of 
# the above approach
MAX = 10000
 
hashTable = [0] * MAX
 
# function to find minimum operations
def minOperations(arr, n):
     
    # sort array
    arr.sort()
 
    # prepare hash of array
    for i in range(n):
        hashTable[arr[i]] += 1
 
    res = 0
    for i in range(n) :
        if (hashTable[arr[i]]) :
            for j in range(i, n):
                if (arr[j] % arr[i] == 0):
                    hashTable[arr[j]] = 0
            res += 1
 
    return res
 
# Driver Code
if __name__ == "__main__":
    arr = [ 4, 6, 2, 8, 7, 21, 24, 49, 44 ]
    n = len(arr)
 
    print(minOperations(arr, n))
 
# This code is contributed 
# by ChitraNayal

C#

using System;
 
// C# implementation of the above approach  
public class Solution
{
public const int MAX = 10000;
 
public static int[] hashTable = new int[MAX];
 
// function to find minimum operations  
public static int minOperations(int[] arr, int n)
{
    // sort array  
    Array.Sort(arr);
 
    // prepare hash of array  
    for (int i = 0; i < n; i++)
    {
        hashTable[arr[i]]++;
    }
 
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        if (hashTable[arr[i]] != 0)
        {
            for (int j = i; j < n; j++)
            {
                if (arr[j] % arr[i] == 0)
                {
                    hashTable[arr[j]] = 0;
                }
            }
            res++;
        }
    }
 
    return res;
}
 
// Driver program  
public static void Main(string[] args)
{
    int[] arr = new int[] {4, 6, 2, 8, 7, 21, 24, 49, 44};
    int n = arr.Length;
 
    Console.Write(minOperations(arr, n));
 
}
}
 
// This code is contributed by Shrikant13

PHP

<?php
// PHP implementation of the 
// above approach
 
// function to find minimum operations
function minOperations(&$arr, $n)
{
    $hashTable = array();
     
    // sort array
    sort($arr);
 
    // prepare hash of array
    for ($i = 0; $i < $n; $i++)
        $hashTable[$arr[$i]]++;
 
    $res = 0;
    for ($i = 0; $i < $n; $i++) 
    {
        if ($hashTable[$arr[$i]])
        {
            for ($j = $i; $j < $n; $j++)
                if ($arr[$j] % $arr[$i] == 0)
                    $hashTable[$arr[$j]] = 0;
            $res++;
        }
    }
 
    return $res;
}
 
// Driver Code
$arr = array(4, 6, 2, 8, 7, 21, 
                    24, 49, 44);
$n = sizeof($arr);
 
echo minOperations($arr, $n);
 
// This code is contributed 
// by Shivi_Aggarwal 
?>

Javascript

<script>
 
// javascript implementation of the above approach
 
var MAX = 10000;
 
var hashTable = Array(MAX).fill(0);
 
// function to find minimum operations
function minOperations(arr, n)
{
    // sort array
    arr.sort((a,b)=>a-b);
 
    // prepare hash of array
    for (var i = 0; i < n; i++)
        hashTable[arr[i]]++;
 
    var res = 0;
    for (var i = 0; i < n; i++) {
        if (hashTable[arr[i]]) {
            for (var j = i; j < n; j++)
                if (arr[j] % arr[i] == 0)
                    hashTable[arr[j]] = 0;
            res++;
        }
    }
 
    return res;
}
 
// Driver program
var arr = [ 4, 6, 2, 8, 7, 21, 24, 49, 44 ];
var n = arr.length;
document.write( minOperations(arr, n));
 
</script>

Output

Time Complexity: O(N logN), where N is the size of the array
Space Complexity: O(MAX)

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 zambiatek!