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 4Explanation: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