Data Modelling & AI Data Structure & Algorithm

Minimize modulo operations to make given Array a permutation of [1, N]

23 June 2025

0

Given an array arr[] of size N, the task is to find the minimum number of operations required to make the array a permutation of numbers in range [1, N] where, in each operation, an element at any index i can be replaced by arr[i]%k (k = any value greater than 0). Return -1 if the array cannot be made a permutation of numbers in range [1, N].

Examples:

Input: arr [] = {1, 7}, N = 2
Output: 1
Explanation: The only possible sequence of operations which minimizes the no of operations is
Choose i = 1, k = 5. Perform arr[1] = arr[1] % 5 = 2.

Input: arr [] = {1,5,4}, N = 3
Output: -1
Explanation: It is impossible to obtain a permutation of integers from 1 to N.

Approach: The problem can be solved on the basis of the following observation.

x % y < (x/2) if x ≥ y, and
x % y = x if x < y.

As bigger is x, the longer the range of values that can be obtained after one mod operation.
So try to, assign smaller arr[i] to smaller numbers in the resulting permutation.

Although, if arr[i] satisfies 1 ≤ arr[i] ≤ N, just leave it there and use it in the resulting permutation.
if multiple arr[i] satisfy the same condition and have the same value, just choose one.
Let’s suppose in the optimal solution, l is changed to m and n to l for some n > l > m (l, m, n are values, not indices).
Then keeping l intact and changing n to m uses 1 less operation.
And, if it is possible to change n to l, then it must be possible to change n to m.

Follow the steps mentioned below to implement the approach:

Sort the array.
If 1 ≤ arr[i] ≤ N and it is the first occurrence of the element with value arr[i], leave it there.
Else, let the current least unassigned value in the resulting permutation be x:
- If x < arr[i]/2, assign the current element to value x and add the number of operations by 1.
- Else, output −1 directly.

Below is the implementation of the above approach.

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
// used to make permutation of 1 to N
void minoperation(vector<int> arr, int N)
{
    set<int> st;
    vector<int> rem;
     
    // Storing one instance of every element 
    // from 1 to N
    for (int i = 1; i <= N; i++) {
        st.insert(i);
    }
 
    for (int i = 0; i < N; i++) {
        if (st.find(arr[i]) != st.end())
            st.erase(arr[i]);
        else
            rem.push_back(arr[i]);
    }
     
    // Sorting in descending order
    sort(rem.begin(), rem.end());
    reverse(rem.begin(), rem.end());
 
    int pt = 0;
    bool flag = false;
 
    for (auto& x : rem) {
        auto it = st.end();
        it--;
        int p = (*it);
        if (p > (x - 1) / 2) {
            flag = true;
            break;
        }
        st.erase(it);
    }
 
    if (flag) {
        // Not possible to make permutation.
        cout << "-1";
    }
    else {
        // Minimum number of operation required.
        cout << rem.size();
    }
}
 
// Driver code
int main()
{
    int N = 3;
    vector<int> arr = { 1, 5, 4 };
    minoperation(arr, N);
    return 0;
}

Java

// Java code to implement above approach
import java.util.*;
class GFG{
 
  // Function to find minimum operations
  // used to make permutation of 1 to N
  static void minoperation(int[] arr, int N)
  {
    HashSet<Integer> st = new HashSet<Integer>();
    Vector<Integer> rem = new Vector<Integer>();
 
    // Storing one instance of every element 
    // from 1 to N
    for (int i = 1; i <= N; i++) {
      st.add(i);
    }
 
    for (int i = 0; i < N; i++) {
      if (st.contains(arr[i]))
        st.remove(arr[i]);
      else
        rem.add(arr[i]);
    }
 
    // Sorting in descending order
    Collections.sort(rem,Collections.reverseOrder());
 
    boolean flag = false;
 
    for (int x : rem) {
      int it = st.size();
      it--;
      int p = new ArrayList<>(st).get(it);
      if (p > (x - 1) / 2) {
        flag = true;
        break;
      }
      st.remove(it);
    }
 
    if (flag) {
      // Not possible to make permutation.
      System.out.print("-1");
    }
    else {
      // Minimum number of operation required.
      System.out.print(rem.size());
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 3;
    int[] arr = { 1, 5, 4 };
    minoperation(arr, N);
  }
}
 
// This code is contributed by 29AjayKumar

C#

// C# code to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find minimum operations
  // used to make permutation of 1 to N
  static void minoperation(int[] arr, int N)
  {
    HashSet<int> st = new HashSet<int>();
    List<int> rem = new List<int>();
 
    // Storing one instance of every element 
    // from 1 to N
    for (int i = 1; i <= N; i++)
    {
      st.Add(i);
    }
 
    for (int i = 0; i < N; i++)
    {
      if (st.Contains(arr[i]))
        st.Remove(arr[i]);
      else
        rem.Add(arr[i]);
    }
 
    // Sorting in descending order
    rem.Sort();
    rem.Reverse();
 
    bool flag = false;
 
    foreach (int x in rem)
    {
      int it = st.Count;
      it--;
      int p = new List<int>(st)[it];
      if (p > (x - 1) / 2)
      {
        flag = true;
        break;
      }
      st.Remove(it);
    }
 
    if (flag)
    {
       
      // Not possible to make permutation.
      Console.Write("-1");
    }
    else
    {
       
      // Minimum number of operation required.
      Console.Write(rem.Count);
    }
  }
 
  // Driver code
  public static void Main()
  {
    int N = 3;
    int[] arr = { 1, 5, 4 };
    minoperation(arr, N);
  }
}
 
// This code is contributed by Saurabh jaiswal

Python3

# Python 3 code to implement above approach
 
# Function to find minimum operations
# used to make permutation of 1 to N
def minoperation(arr, N):
    st = set([])
    rem = []
 
    # Storing one instance of every element
    # from 1 to N
    for i in range(1, N + 1):
        st.add(i)
 
    for i in range(N):
        if (arr[i] in st):
            st.remove(arr[i])
 
        else:
            rem.append(arr[i])
 
    # Sorting in descending order
    rem.sort()
    rem.reverse()
 
    pt = 0
    flag = False
 
    for x in rem:
        it = len(st)
        it -= 1
        p = list(st)[it]
        if (p > (x - 1) / 2):
            flag = True
            break
 
        st.remove(it)
 
    if (flag):
        # Not possible to make permutation.
        print("-1")
 
    else:
        # Minimum number of operation required.
        print(len(rem))
 
# Driver code
if __name__ == "__main__":
 
    N = 3
    arr = [1, 5, 4]
    minoperation(arr, N)
 
    # This code is contributed by ukasp.

Javascript

<script>
        // JavaScript code for the above approach 
 
        // Function to find minimum operations
        // used to make permutation of 1 to N
        function minoperation(arr, N)
        {
            let st = new Set();
            let rem = [];
 
            // Storing one instance of every element 
            // from 1 to N
            for (let i = 1; i <= N; i++) {
                st.add(i);
            }
 
            for (let i = 0; i < N; i++) {
                if (st.has(arr[i]))
                    st.delete(arr[i]);
                else
                    rem.push(arr[i]);
            }
 
            // Sorting in descending order
            rem.sort(function (a, b) { return b - a })
            rem.reverse();
 
            let pt = 0;
            let flag = false;
 
            for (let x of rem) {
                let it = [...st].pop();
 
                let p = (it);
                if (p > Math.floor((x - 1) / 2)) {
                    flag = true;
                    break;
                }
                st.delete(it);
            }
 
            if (flag)
            {
             
                // Not possible to make permutation.
                document.write(-1)
            }
            else {
                // Minimum number of operation required.
                document.write(rem.size)
            }
        }
 
        // Driver code
        let N = 3;
        let arr = [1, 5, 4];
        minoperation(arr, N);
 
  // This code is contributed by Potta Lokesh
    </script>

Output

-1

Time Complexity: O(N * logN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

2 COMMENTS

Houten 17 November 2025 At 9:54 am

… [Trackback]

[…] Info to that Topic: geeksforgeeks.org/minimize-modulo-operations-to-make-given-array-a-permutation-of-1-n/ […]

Log in to leave a comment
ethereum news 7 December 2025 At 12:30 am

… [Trackback]

[…] Information to that Topic: geeksforgeeks.org/minimize-modulo-operations-to-make-given-array-a-permutation-of-1-n/ […]

Log in to leave a comment

Minimize modulo operations to make given Array a permutation of [1, N]

C++

Java

C#

Python3

Javascript

Multimodal RAG Made Simple: RAG-Anything + Milvus Instead of 20 Separate Tools

Introducing the Embedding Function: How Milvus 2.6 Streamlines Vectorization and Semantic Search

Choosing a vector database for ANN search at Reddit

2 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

House Democrats Official Online Resume Bank Exposed the PII of Thousands of Government Job Seekers by

The Galaxy S25 Ultra goes beyond what most people need, making the S25+ the smarter pick

This Android 16 tablet feature is making me consider replacing my iPad

7 Android tools I use to avoid overspending during holiday sales

EDITOR PICKS

House Democrats Official Online Resume Bank Exposed the PII of Thousands of Government Job Seekers by

The Galaxy S25 Ultra goes beyond what most people need, making the S25+ the smarter pick

This Android 16 tablet feature is making me consider replacing my iPad

POPULAR POSTS

House Democrats Official Online Resume Bank Exposed the PII of Thousands of Government Job Seekers by

The Galaxy S25 Ultra goes beyond what most people need, making the S25+ the smarter pick

This Android 16 tablet feature is making me consider replacing my iPad

POPULAR CATEGORY

ABOUT US

FOLLOW US