Given an array A[] of N non-negative integers and an integer K. Each time, you can do the following two operations
- Find Average of MAX and MEX(rounded up to closest greater integer) of the array.
- Insert calculated average in the array.
After performing the above operation K times, find the count of unique elements present in the array.
Note: MEX is the minimum positive integer not present in the array.
Examples:
Input: A = [ 0, 5, 1, 2, 1, 8 ], K=1
Output: 6
Explanation: In first operation, Max = 8 and MEX = 3.
So average is ( 8 + 3 ) / 2 = 5.5 = 6 (rounded up).
Insert 6 in the array, then Array becomes: [ 0, 5, 1, 2, 1, 8, 6 ].
So, Count of unique element is 6.Input: A = [ 0, 1, 2 ], K = 2
Output: 5
Explanation: In first operation, Max = 2 and MEX = 3.
So average is ( 2 + 3 ) / 2 = 2.5 = 3 (rounded up).
Add 3 in the array, then Array becomes: [ 0, 1, 2, 3 ].
In Second Operation, Again Max = 3 and MEX = 4, Average = 4.
So Add 4 in the array. Now the Array becomes [ 0, 1, 2, 3, 4 ].
So, Count of unique element is 5.
Naive Approach: Traverse the given array K times, and in each iteration:
- Find out the MAX and MEX in the array.
- Calculate the average.
- Insert that element in the array.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: The solution to the problem is based on the following two cases:
Case-1 (When Max > MEX): The average of Max and MEX will always lie between Max and MEX and there will be no changes of Max value or MEX value.
So it does not matter if the average is added once or K times.
If average is unique then unique element count will increase by 1, otherwise, the unique count will be the same.Case-2 (When Max < MEX): The average of Max and MEX will always be greater than the existing Max. So at every step a new unique element will be added to the array, i.e. total K elements added in K operations.
e.g. arr[] = {0, 1, 2} and K = 2.
- At first step Max and MEX are 2 and 3 respectively. So (2+3)/2 = 3 will be added. The array will be {0, 1, 2, 3}.
- At 2nd step Max and MEX are 3 and 4 respectively. So (3+4)/2 = 4 will be added. The array will be {0, 1, 2, 3, 4}. Therefore 2 unique elements will be added in 2 operation.
Follow the steps mentioned below to solve the problem:
- Create a hash array, to store the unique elements.
- Push all given array elements into the hash array.
- Calculate Max and MEX for the given array.
- If Max is greater than MEX, calculate the average and push into the hash array.
- If MEX is greater than Max, just add K to the count of unique elements in the array because, in all K operations, the unique element is added to array.
- Return the count of the unique elements in the hash array.
Below is the implementation of the above approach.
C++
//c++ program for Count number Unique element after //adding average of MEX and MAX in array K times. #include <bits/stdc++.h> using namespace std; int uniqueElement(vector< int >& A, int K) { // Hash array unordered_map< int , int > mp; int max_no = 0; // Find out MAX of given Array for ( int i = 0; i < A.size(); i++) { mp[A[i]]++; max_no = max(max_no, A[i]); } int mex = INT_MIN; // Find out MEX of given Array for ( int i = 0; i < max_no; i++) { if (mp.find(i) == mp.end()) { mex = i; break ; } } if (mex == INT_MIN) mex = max_no + 1; // Hash array contains only unique elements // So number of unique elements in array = // size of Hash array int unique = mp.size(); if (K != 0) { if (max_no > mex) { // Calculated rounded average of MAX and MEX int avg = round(( float )(max_no + mex) / 2); // If MAX > MEX and avg in not present // in array Increment count of unique //element by one. if (mp[avg] == 0) unique++; } // If MEX > MAX, for every operation, one // new unique element is added in array else { unique += K; } } return unique; } //Driver code int main() { vector< int > A = { 3, 0, 2, 4, 1, 2, 3, 5 }; int K = 3; cout << uniqueElement(A, K); return 0; } |
Java
import java.util.*; import java.io.*; class GFG{ // Function to find remaining element public static int uniqueElement(ArrayList<Integer> A, int K){ // Hash array TreeMap<Integer, Integer> mp = new TreeMap<Integer,Integer>(); int max_no = 0 ; // Find out MAX of given Array for ( int i = 0 ; i<A.size() ; i++){ if (mp.containsKey(A.get(i))){ mp.put(A.get(i), mp.get(A.get(i))+ 1 ); } else { mp.put(A.get(i), 1 ); } max_no = Math.max(max_no, A.get(i)); } int mex = - 1 ; // Find out MEX of given Array for ( int i= 0 ; i<max_no ; i++){ if (mp.containsKey(i)){ } else { mex = i; break ; } } if (mex==- 1 ){ mex = max_no+ 1 ; } // Hash array contains only unique elements // So number of unique elements in array = // size of Hash array int unique = mp.size(); if (K != 0 ){ if (max_no > mex){ // Calculated rounded average of MAX and MEX int avg = Math.round(( float )(max_no+mex)/ 2 ); // If MAX > MEX and avg in not present // in array Increment count of unique //element by one. if (!mp.containsKey(avg) || mp.get(avg) == 0 ){ unique++; } } // If MEX > MAX, for every operation, one // new unique element is added in array else { unique += K; } } return unique; } // Driver code public static void main(String args[]) { // Size of array ArrayList<Integer> A = new ArrayList<Integer>( List.of( 3 , 0 , 2 , 4 , 1 , 2 , 3 , 5 ) ); int K = 3 ; // Function call System.out.println(uniqueElement(A, K)); } } // This code is contributed by subhamgoyal2014. |
Python3
# python3 program for Count number Unique element after # adding average of MEX and MAX in array K times. INT_MIN = - 2147483647 - 1 def uniqueElement(A, K): # Hash array mp = {} max_no = 0 # Find out MAX of given Array for i in range ( 0 , len (A)): mp[A[i]] = mp[A[i]] + 1 if A[i] in mp else 1 max_no = max (max_no, A[i]) mex = INT_MIN # Find out MEX of given Array for i in range ( 0 , max_no): if ( not i in mp): mex = i break if (mex = = INT_MIN): mex = max_no + 1 # Hash array contains only unique elements # So number of unique elements in array = # size of Hash array unique = len (mp) if (K ! = 0 ): if (max_no > mex): # Calculated rounded average of MAX and MEX avg = round ((max_no + mex) / 2 ) # If MAX > MEX and avg in not present # in array Increment count of unique # element by one. if (mp[avg] = = 0 ): unique + = 1 # If MEX > MAX, for every operation, one # new unique element is added in array else : unique + = K return unique # Driver code if __name__ = = "__main__" : A = [ 3 , 0 , 2 , 4 , 1 , 2 , 3 , 5 ] K = 3 print (uniqueElement(A, K)) # This code is contributed by rakeshsahni |
C#
// c# program for Count number Unique element after // adding average of MEX and MAX in array K times. using System; using System.Collections.Generic; class GFG { static int uniqueElement( int [] A, int K) { // Hash array Dictionary< int , int > mp = new Dictionary< int , int >(); int max_no = 0; // Find out MAX of given Array for ( int i = 0; i < A.Length; i++) { if (mp.ContainsKey(A[i])) { mp[A[i]] = mp[A[i]] + 1; } else { mp.Add(A[i], 1); } max_no = Math.Max(max_no, A[i]); } int mex = Int32.MinValue; // Find out MEX of given Array for ( int i = 0; i < max_no; i++) { if (!mp.ContainsKey(i)) { mex = i; break ; } } if (mex == Int32.MinValue) mex = max_no + 1; // Hash array contains only unique elements // So number of unique elements in array = // size of Hash array int unique = mp.Count; if (K != 0) { if (max_no > mex) { // Calculated rounded average of MAX and MEX float temp = (max_no + mex) / 2; int avg = ( int )Math.Round(temp); // If MAX > MEX and avg in not present // in array Increment count of unique // element by one. if (mp[avg] == 0) unique++; } // If MEX > MAX, for every operation, one // new unique element is added in array else { unique += K; } } return unique; } // Driver code public static void Main() { int [] A = { 3, 0, 2, 4, 1, 2, 3, 5 }; int K = 3; Console.Write(uniqueElement(A, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach function uniqueElement(A, K) { // Hash array let mp = new Map(); let max_no = 0; // Find out MAX of given Array for (let i = 0; i < A.length; i++) { if (mp.has(A[i])) { mp.set(A[i], mp.get(A[i] + 1)) } else { mp.set(A[i], 1) } max_no = Math.max(max_no, A[i]); } let mex = Number.MIN_VALUE; // Find out MEX of given Array for (let i = 0; i < max_no; i++) { if (!mp.has(i)) { mex = i; break ; } } if (mex == Number.MIN_VALUE) mex = max_no + 1; // Hash array contains only unique elements // So number of unique elements in array = // size of Hash array let unique = mp.size; if (K != 0) { if (max_no > mex) { // Calculated rounded average of MAX and MEX let avg = Math.fround((max_no + mex) / 2); // If MAX > MEX and avg in not present // in array Increment count of unique //element by one. if (mp.get(avg) == 0) unique++; } // If MEX > MAX, for every operation, one // new unique element is added in array else { unique += K; } } return unique; } // Driver code let A = [3, 0, 2, 4, 1, 2, 3, 5]; let K = 3; document.write(uniqueElement(A, K)); // This code is contributed by Potta Lokesh </script> |
Output:
9
Time Complexity: O(N*logN )
Auxiliary Space: O(N )
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!