Given an array arr[] of size N, the task is to make all array elements equal to 0 by replacing all elements of a subsequences of equal elements by any integer, minimum number of times.
Examples:
Input: arr[] = {3, 7, 3}, N = 3
Output: 2
Explanation:
Selecting a subsequence { 7 } and replacing all its elements by 0 modifies arr[] to { 3, 3, 3 }.
Selecting the array { 3, 3, 3 } and replacing all its elements by 0 modifies arr[] to { 0, 0, 0 }Input: arr[] = {1, 5, 1, 3, 2, 3, 1}, N = 7
Output: 4
Approach: The problem can be solved using Greedy technique. The idea is to count the distinct elements present in the array which is not equal to 0 and print the count obtained. Follow the steps below to solve the problem:
- Initialize a Set to store the distinct elements present in the array, which is not equal to 0.
- Traverse the array arr[] and insert the array elements into the Set.
- Finally, print the size of the Set.
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 minimum count of operations// required to convert all array elements to zero// br replacing subsequence of equal elements to 0void minOpsToTurnArrToZero(int arr[], int N){ // Store distinct elements // present in the array unordered_set<int> st; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is already present in // the Set or arr[i] is equal to 0 if (st.find(arr[i]) != st.end() || arr[i] == 0) { continue; } // Otherwise, increment ans by // 1 and insert current element else { st.insert(arr[i]); } } cout << st.size() << endl;}// Driver Codeint main(){ // Given array int arr[] = { 3, 7, 3 }; // Size of the given array int N = sizeof(arr) / sizeof(arr[0]); minOpsToTurnArrToZero(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find minimum count of operations // required to convert all array elements to zero // br replacing subsequence of equal elements to 0 static void minOpsToTurnArrToZero(int[] arr, int N) { // Store distinct elements // present in the array Set<Integer> st = new HashSet<Integer>(); // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is already present in // the Set or arr[i] is equal to 0 if (st.contains(arr[i]) || arr[i] == 0) { continue; } // Otherwise, increment ans by // 1 and insert current element else { st.add(arr[i]); } } System.out.println(st.size()); } // Driver Code public static void main(String args[]) { // Given array int arr[] = { 3, 7, 3 }; // Size of the given array int N = arr.length; minOpsToTurnArrToZero(arr, N); }}// This code is contributed by 18bhupendrayadav18 |
Python3
# Python3 program for the above approach# Function to find minimum count of # operations required to convert all # array elements to zero by replacing # subsequence of equal elements to 0def minOpsToTurnArrToZero(arr, N): # Store distinct elements # present in the array st = dict() # Traverse the array for i in range(N): # If arr[i] is already present in # the Set or arr[i] is equal to 0 if (i in st.keys() or arr[i] == 0): continue # Otherwise, increment ans by # 1 and insert current element else: st[arr[i]] = 1 print(len(st))# Driver Code# Given arrayarr = [ 3, 7, 3 ]# Size of the given arrayN = len(arr) minOpsToTurnArrToZero(arr, N)# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find minimum count of operations // required to convert all array elements to zero // br replacing subsequence of equal elements to 0 static void minOpsToTurnArrToZero(int[] arr, int N) { // Store distinct elements // present in the array HashSet<int> st = new HashSet<int>(); // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is already present in // the Set or arr[i] is equal to 0 if (st.Contains(arr[i]) || arr[i] == 0) { continue; } // Otherwise, increment ans by // 1 and insert current element else { st.Add(arr[i]); } } Console.WriteLine(st.Count); } // Driver Code public static void Main(String []args) { // Given array int []arr = { 3, 7, 3 }; // Size of the given array int N = arr.Length; minOpsToTurnArrToZero(arr, N); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to find minimum count of operations// required to convert all array elements to zero// br replacing subsequence of equal elements to 0function minOpsToTurnArrToZero(arr, N){ // Store distinct elements // present in the array var st = new Set(); // Traverse the array for(var i = 0; i < N; i++) { // If arr[i] is already present in // the Set or arr[i] is equal to 0 if (st.has(arr[i]) || arr[i] == 0) { continue; } // Otherwise, increment ans by // 1 and insert current element else { st.add(arr[i]); } } document.write(st.size)}// Driver Code// Given arrayvar arr = [ 3, 7, 3 ];// Size of the given arrayvar N = arr.length;minOpsToTurnArrToZero(arr, N);// This code is contributed by noob2000</script> |
Output:
2
Time Complexity: O(N)
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!