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!

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

C++

Java

C#

Python3

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

Samsung’s upcoming tri-fold phone could flex its power with a massive battery setup

EDITOR PICKS

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

POPULAR POSTS

The Pixel 10 Pro Fold sets itself apart with this one thing you don’t see

T-Mobile’s Pixel 10 Pro Fold deal knocks $1,000 off and includes a free pair of Pixel Buds 2a

Samsung Galaxy XR leak provides us with our best look yet at what to expect

POPULAR CATEGORY

ABOUT US

FOLLOW US