# Change the array into a permutation of numbers from 1 to n

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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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`

## tags:

Arrays Hash cpp-unordered_map Arrays Hash