Change the Array into Permutation of Numbers From 1 to N

In this problem, we have 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.

Example

Input:

2 2 3 3

Output:

2 1 3 4

Input :

3 2 1 7 8 3

Output:

3 2 1 4 5 6

Main idea for Change the Array into Permutation of Numbers From 1 to N

First, we will store all the missing elements in a set. After that, we will maintain a hash table which will store whether we have printed or not and if we have already printed an element and it comes again in the array then it means we have to print a missing element instead of this element so we will print an element from our set and then erase that element from our set.

Algorithm

1. Make a set of all the numbers from 1 to n;
2. Iterate the array and remove all the array elements from the set.
3. Declare a hash table and initialize all its values with false.
4. Iterate the array for I in range 1 to n-1
   • If we have not printed arr[i] then print arr[i] and mark it as true in the hash table.
   • Else if we have already printed arr[i], then print the first element from the set and remove that element from the set.
5. Return.

Implementation for Change the Array into Permutation of Numbers From 1 to N

C++ program

#include <bits/stdc++.h>
using namespace std;
void makePermutation(vector<int> a, int n)
{
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        s.insert(i);
    }
    for (int i = 0; i < n; i++)
    {
        if (s.count(a[i]))
        {
            s.erase(a[i]);
        }
    }
    vector<bool> m(n + 1, false);
    for (int i = 0; i < n; i++)
    {
        if ((a[i] <= n) and (a[i] > 0) and (m[a[i]] == 0))
        {
            m[a[i]] = true;
            cout << a[i] << " ";
        }
        else
        {
            int missing_number = *s.begin();
            m[missing_number] = true;
            s.erase(s.begin());
            cout << missing_number << " ";
        }
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    makePermutation(a, n);
    return 0;
}

2 2 3 3

2 1 3 4

JAVA program

import java.util.*;
public class Main
{
    public static void makePermutation(int[] a, int n)
    {
        Set<Integer> s = new HashSet<Integer>(); 
        for (int i = 1; i <= n; i++)
        {
            s.add(i);
        }
        for (int i = 0; i < n; i++)
        {
            if (s.contains(a[i]))
            {
                s.remove(a[i]);
            }
        }
        boolean[] m = new boolean[n+1];
        for (int i = 0; i < n; i++)
        {
            if ((a[i] <= n) && (a[i] > 0) && (m[a[i]] == false))
            {
                m[a[i]] = true;
                System.out.print(a[i]+" ");
            }
            else
            {
                int missing_number = (s.iterator()).next();
                m[missing_number] = true;
                s.remove(missing_number);
                System.out.print(missing_number+" ");
            }
        }
        return;
    }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      for(int i=0;i<n;i++){
          a[i] = sc.nextInt();
      }
      makePermutation(a, n);
  }
}

5
1 5 3 7 6

1 5 3 2 4

Complexity Analysis for Change the Array into Permutation of Numbers From 1 to N

Time complexity

O(NlogN) because to prepare the set of missing elements, we iterate from 1 to n, and each insertion takes logn time so, the total time complexity is O(N*logN).

Space complexity

O(N) because here we have taken and extra set and a hash table both of size N, so our space complexity is O(N)

References