Given an array A of n elements. We need to change the array into a permutation of numbers from 1 to n using minimum replacements in the array.
Examples:
Input : A[] = {2, 2, 3, 3} Output : 2 1 3 4 Explanation: To make it a permutation of 1 to 4, 1 and 4 are missing from the array. So replace 2, 3 with 1 and 4. Input : A[] = {1, 3, 2} Output : 1 3 2 Input : A[] = {10, 1, 2} Output : 3 1 2
Approach:Observe that we don’t need to change the numbers which are in the range [1, n] and which are distinct(has only one occurrence). So, we use a greedy approach. If we meet the number we have never met before and this number is between 1 and n, we leave this number unchanged. And remove the duplicate elements and add the missing elements in the range [1, n]. Also replace the numbers, not in the range.
C++
// CPP program to make a permutation of numbers // from 1 to n using minimum changes. #include <bits/stdc++.h> using namespace std; void makePermutation( int a[], int n) { // Store counts of all elements. unordered_map< int , int > count; for ( int i = 0; i < n; i++) count[a[i]]++; int next_missing = 1; for ( int i = 0; i < n; i++) { if (count[a[i]] != 1 || a[i] > n || a[i] < 1) { count[a[i]]--; // Find next missing element to put // in place of current element. while (count.find(next_missing) != count.end()) next_missing++; // Replace with next missing and insert the // missing element in hash. a[i] = next_missing; count[next_missing] = 1; } } } // Driver Code int main() { int A[] = { 2, 2, 3, 3 }; int n = sizeof (A) / sizeof (A[0]); makePermutation(A, n); for ( int i = 0; i < n; i++) cout << A[i] << " " ; return 0; } |
Python3
# Python3 code to make a permutation # of numbers from 1 to n using # minimum changes. def makePermutation (a, n): # Store counts of all elements. count = dict () for i in range (n): if count.get(a[i]): count[a[i]] + = 1 else : count[a[i]] = 1 ; next_missing = 1 for i in range (n): if count[a[i]] ! = 1 or a[i] > n or a[i] < 1 : count[a[i]] - = 1 # Find next missing element to put # in place of current element. while count.get(next_missing): next_missing + = 1 # Replace with next missing and # insert the missing element in hash. a[i] = next_missing count[next_missing] = 1 # Driver Code A = [ 2 , 2 , 3 , 3 ] n = len (A) makePermutation(A, n) for i in range (n): print (A[i], end = " " ) # This code is contributed by "Sharad_Bhardwaj". |
Output:
1 2 4 3
leave a comment
0 Comments