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