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 ith 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 approachint findValue(long long N, long long Y){ return min(N, Y + 1 - N);}// Function to generate the permutationvoid 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 Codeint 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 approachdef findValue(N, Y): return min(N, Y + 1 - N)# Function to generate the permutationdef 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 Codeif __name__ == "__main__": N, Y = 5, 10 generatePermutation(N, Y)# This code is contributed by rakeshsahni |
C#
// C# implementation of above approachusing 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 approachfunction findValue(N, Y){ return Math.min(N, Y + 1 - N);}// Function to generate the permutationfunction 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 Codelet 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)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
