Minimize operations to make Array unique by adding any value to any Subsequence
Given an array A[] consisting of N integers, the task is to find the minimum number of operations required to make all array elements different such that in one operation we can choose any subsequence of the array and any integer Y and then add Y to all the elements of the chosen subsequence.
Examples:
Input: A = {1, 3, 2, 1, 2, 2}
Output: 2
?Explanation: In first operation choose the subsequence {A1, A6} and add Y = 4 to the elements. The array becomes A = [5, 3, 2, 1, 2, 6]. And in second operation choose the subsequence {A3} and add Y = 5 to the elements. The array becomes A = [5, 3, 7, 1, 2, 6].Input: A = {1, 3, 5, 4, 2}
Output: 0
Approach: The problem can be solved based on the following observations:
Count the frequency of each element in an array. After that find the maximum frequency of an element (say max). So we have change max-1 elements to some other value using the above operation.
This can be done by
- Changing half of the elements at a time (i.e. max/2).
- Then we can pick max/4 from each half and change them to some other value. This will take 1 operation.
- On the next operation we can pick max/8 from all the same valued groups and change them and continue this process.
So the total number of steps will be ceil(log2max) as we will have to continue this halving operation till all are unique.
Follow the below steps to solve the problem:
- Create a HashMap which will contain the frequency of each element in an array.
- Iterate to find the maximum frequency(say max) of the array element.
- The answer will be ceil(log2max) because of the reason mentioned above.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find minimum operation // required to make all array element // different int minOperation( int arr[], int n) { unordered_map< int , int > mp; for ( int i = 0; i < n; i++) mp[arr[i]]++; int maxi = 0; for ( auto x : mp) { maxi = max(maxi, x.second); } int result = ( int ) ceil (( log (maxi) / log (2))); return result; } // Driver code int main() { int A[] = { 1, 3, 2, 1, 2, 2 }; int N = sizeof (A) / sizeof (A[0]); // Function call cout << minOperation(A, N); return 0; } // This code is contributed by aarohirai2616. |
Java
// Java code to implement the approach import java.io.*; import java.util.*; public class GFG { // Function to find minimum operation // required to make all array element // different public static int minOperation( int arr[], int n) { Map<Integer, Integer> mp = new HashMap<>(); for ( int i = 0 ; i < n; i++) { int value = arr[i]; mp.put(value, mp.getOrDefault(value, 0 ) + 1 ); } int max = 0 ; for (Integer i : mp.keySet()) { max = Math.max(max, mp.get(i)); } int result = ( int )Math.ceil((Math.log(max) / Math.log( 2 ))); return result; } // Driver Code public static void main(String[] args) { int [] A = { 1 , 3 , 2 , 1 , 2 , 2 }; int N = A.length; // Function Call System.out.println(minOperation(A, N)); } } |
Python3
# Python3 code to implement the above approach import math # Function to find minimum operation # required to make all array element # different def minOperation(arr, n) : mp = dict .fromkeys(arr, 0 ); for i in range (n) : mp[arr[i]] + = 1 ; maxi = 0 ; for x in mp : maxi = max (maxi, mp[x]); result = math.ceil((math.log(maxi) / math.log( 2 ))) return result; if __name__ = = "__main__" : A = [ 1 , 3 , 2 , 1 , 2 , 2 ]; N = len (A); # Function call print (minOperation(A, N)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; using System.Collections; using System.Collections.Generic; public class GFG { // Function to find minimum operation // required to make all array element // different public static int minOperation( int [] arr, int n) { Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { mp[arr[i]] = mp.ContainsKey(arr[i]) ? mp[arr[i]] + 1 : 1; } int max = 0; foreach ( var i in mp) { max = Math.Max(max, i.Key); } int result = ( int )Math.Ceiling((Math.Log(max) / Math.Log(2))); return result; } static public void Main() { // Code int [] A = { 1, 3, 2, 1, 2, 2 }; int N = A.Length; // Function Call Console.WriteLine(minOperation(A, N)); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach // Function to find minimum operation // required to make all array element // different const minOperation = (arr, n) => { let mp = {}; for (let i = 0; i < n; i++) mp[arr[i]] = arr[i] in mp ? mp[arr[i]] + 1 : 1; let maxi = 0; for (let x in mp) { maxi = Math.max(maxi, mp[x]); } let result = Math.ceil((Math.log(max) / Math.log(2))); return result; } let A = [1, 3, 2, 1, 2, 2]; let N = A.length; // Function call console.log(minOperation(A, N)); // This code is contributed by rakeshsahni |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us