Tutorialspoint.dev

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
          

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


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter