Generate permutation of 1 to N with sum of min of prefix for each element as Y

Namachila November 19, 2025

0 0 7 minutes read

Given two integers N, Y, generate a permutation of length N such that sum of all prefix minimum of that permutation is Y.

Example:

Input: N = 5, Y = 10
Output: 5 2 1 4 3
Explanation: Array of prefix minimum for [5, 2, 1, 4, 3] is [5, 2, 1, 1, 1]. Sum of this array of prefix minimum is 10 (= Y).

Input: N = 5, Y = 5
Output: 1 2 3 4 5
Explanation: Array of prefix minimum for [1, 2, 3, 4, 5] is [1, 1, 1, 1, 1]. Sum of this array of prefix minimum is 5 (= Y).

Approach: The approach to solve this problem is based on below idea:

Suppose the remaining array to be created at some point of time be len and the remaining sum to be rem.

Greedily choose a value for this index by the given method below:

let’s take Z value at this index, then we should have at least (Z + len – 1) = rem (By taking 1 at remaining indices).

So, we get Z = (rem + 1 – len). Now, this value might be greater than len but we can’t take it. So, we will choose min(Z, len).

Follow the below steps to solve this problem:

Now, a prefix minimum array for the required permutation is already built from the above greedy method.
It might have duplicates as well. So, to remove that iterate over this array in reverse order and whenever arr[i] = arr[i-1], then put the smallest element not present at any index at i^th index.
In this way, ensured that the sum of prefix minimum should be Y and the array created should be permutation as well.
Print the final array

Below is the implementation of the above approach:

C++

// C++ program for Generate permutation
// of length N such that sum of all prefix
// minimum of that permutation is Y.
#include <iostream>
#include <set>
#include <vector>
using namespace std;
 
// Find the value greedily for the
// current index  as discussed in approach
int findValue(long long N, long long Y)
{
    return min(N, Y + 1 - N);
}
 
// Function to generate the permutation
void generatePermutation(long long N, long long Y)
{
    // Store the prefix minimum array first
    // then we will convert it to permutation
    vector<int> ans(N);
 
    // If Y should belong to [N, (N*(N + 1)/2)],
    // otherwise we will print -1;
    if (Y < N || (2 * Y) > (N * (N + 1))) {
        cout << -1 << endl;
        return;
    }
 
    // Remaining elements to be taken
    set<int> s;
 
    for (int i = 1; i <= N; i++) {
        s.insert(i);
    }
 
    // Generate prefix minimum array
    for (int i = 0; i < N; i++) {
        // Length remaining
        int len = N - i;
        int val = findValue(len, Y);
        ans[i] = val;
        Y -= val;
        if (s.find(val) != s.end())
            s.erase(val);
    }
 
    // Remove duplicates to make array permutation
    // So, iterate in reverse order
    for (int i = N - 1; i > 0; i--) {
        if (ans[i] == ans[i - 1]) {
            // Find minimum element not taken
            // in the permutation
            ans[i] = *s.begin();
            s.erase(ans[i]);
        }
    }
 
    // Print the permutation
    for (auto i : ans) {
        cout << i << " ";
    }
    cout << endl;
}
 
// Driver Code
int main()
{
 
    long long N = 5, Y = 10;
 
    generatePermutation(N, Y);
    return 0;
}

Java

// Java program for Generate permutation
// of length N such that sum of all prefix
// minimum of that permutation is Y.
import java.util.*;
 
class GFG {
 
  // Find the value greedily for the
  // current index  as discussed in approach
  static int findValue(int  N, int  Y)
  {
    return Math.min(N, Y + 1 - N);
  }
 
  // Function to generate the permutation
  static void generatePermutation( int N,  int Y)
  {
    // Store the prefix minimum array first
    // then we will convert it to permutation
    int[] ans = new int[N];
 
    // If Y should belong to [N, (N*(N + 1)/2)],
    // otherwise we will print -1;
    if (Y < N || (2 * Y) > (N * (N + 1))) {
      System.out.println(-1);
      return;
    }
 
    // Remaining elements to be taken
    Set<Integer> s = new HashSet<Integer>();
 
    for (int i = 1; i <= N; i++) {
      s.add(i);
    }
 
    // Generate prefix minimum array
    for (int i = 0; i < N; i++) {
      // Length remaining
      int len = N - i;
      int val = findValue(len, Y);
      ans[i] = val;
      Y -= val;
      if (s.contains(val))
        s.remove(val);
    }
 
    // Remove duplicates to make array permutation
    // So, iterate in reverse order
    for (int i = N - 1; i > 0; i--) {
      if (ans[i] == ans[i - 1]) {
        // Find minimum element not taken
        // in the permutation
        ans[i] = s.stream().findFirst().get();
        s.remove(ans[i]);
      }
    }
 
    // Print the permutation
    for (int i = 0; i < N; i++) {
      System.out.print(ans[i] + " ");
    }
  }
 
  // Driver Code
  public static void main (String[] args) {
 
    int N = 5, Y = 10;
 
    generatePermutation(N, Y);
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# python3 program for Generate permutation
# of length N such that sum of all prefix
# minimum of that permutation is Y.
 
# Find the value greedily for the
# current index as discussed in approach
def findValue(N, Y):
    return min(N, Y + 1 - N)
 
# Function to generate the permutation
def generatePermutation(N, Y):
 
    # Store the prefix minimum array first
    # then we will convert it to permutation
    ans = [0 for _ in range(N)]
 
    # If Y should belong to [N, (N*(N + 1)/2)],
    # otherwise we will print -1;
    if (Y < N or (2 * Y) > (N * (N + 1))):
        print(-1)
        return
 
    # Remaining elements to be taken
    s = set()
 
    for i in range(1, N+1):
        s.add(i)
 
    # Generate prefix minimum array
    for i in range(0, N):
        # Length remaining
        len = N - i
        val = findValue(len, Y)
        ans[i] = val
        Y -= val
        if (val in s):
            s.remove(val)
 
    # Remove duplicates to make array permutation
    # So, iterate in reverse order
    for i in range(N-1, -1, -1):
        if (ans[i] == ans[i - 1]):
            # Find minimum element not taken
            # in the permutation
            ans[i] = list(s)[0]
            s.remove(ans[i])
 
    # Print the permutation
    for i in ans:
        print(i, end=" ")
 
    print()
 
# Driver Code
if __name__ == "__main__":
 
    N, Y = 5, 10
 
    generatePermutation(N, Y)
 
# This code is contributed by rakeshsahni

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
 
  // Find the value greedily for the
  // current index  as discussed in approach
  static int findValue(int  N, int  Y)
  {
    return Math.Min(N, Y + 1 - N);
  }
 
  // Function to generate the permutation
  static void generatePermutation( int N,  int Y)
  {
    // Store the prefix minimum array first
    // then we will convert it to permutation
    int[] ans = new int[N];
 
    // If Y should belong to [N, (N*(N + 1)/2)],
    // otherwise we will print -1;
    if (Y < N || (2 * Y) > (N * (N + 1))) {
      Console.Write(-1);
      return;
    }
 
    // Remaining elements to be taken
    HashSet<int> s = new HashSet<int>(); 
 
    for (int i = 1; i <= N; i++) {
      s.Add(i);
    }
 
    // Generate prefix minimum array
    for (int i = 0; i < N; i++) {
      // Length remaining
      int len = N - i;
      int val = findValue(len, Y);
      ans[i] = val;
      Y -= val;
      if (s.Contains(val))
        s.Remove(val);
    }
 
    // Remove duplicates to make array permutation
    // So, iterate in reverse order
    for (int i = N - 1; i > 0; i--) {
      if (ans[i] == ans[i - 1]) {
        // Find minimum element not taken
        // in the permutation
        ans[i] = s.First();
        s.Remove(ans[i]);
      }
    }
 
    // Print the permutation
    for (int i = 0; i < N; i++) {
      Console.Write(ans[i] + " ");
    }
  }
 
  // Driver Code
  static public void Main (){
 
    int N = 5, Y = 10;
 
    generatePermutation(N, Y);
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// JavaScript program for Generate permutation
// of length N such that sum of all prefix
// minimum of that permutation is Y.
 
// Find the value greedily for the
// current index  as discussed in approach
function findValue(N, Y)
{
    return Math.min(N, Y + 1 - N);
}
 
// Function to generate the permutation
function generatePermutation(N, Y)
{
    // Store the prefix minimum array first
    // then we will convert it to permutation
    let ans = new Array(N);
 
    // If Y should belong to [N, (N*(N + 1)/2)],
    // otherwise we will print -1;
    if (Y < N || (2 * Y) > (N * (N + 1))) {
        document.write(-1,"</br>");
        return;
    }
 
    // Remaining elements to be taken
    let s = new Set();
 
    for (let i = 1; i <= N; i++) {
        s.add(i);
    }
 
    // Generate prefix minimum array
    for (let i = 0; i <N; i++) {
        // Length remaining
        let len = N - i;
        let val = findValue(len, Y);
        ans[i] = val;
        Y -= val;
        if (s.has(val))
            s.delete(val);
    }
 
    // Remove duplicates to make array permutation
    // So, iterate in reverse order
    for (let i = N - 1; i > 0; i--) {
        if (ans[i] == ans[i - 1]) {
            // Find minimum element not taken
            // in the permutation
            ans[i] = Array.from(s)[0]
            s.delete(ans[i]);
        }
    }
 
    // Print the permutation
    for (let i of ans) {
        document.write(i," ");
    }
    document.write("</N;>");
}
 
// Driver Code
let N = 5, Y = 10;
generatePermutation(N, Y);
 
// This code is contributed by shinjanpatra
 
</script>

Output

5 2 1 4 3

Time Complexity: O(N * log N).
If we are using a set, we can make it O(N) by using two pointer technique.
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 zambiatek!