Given four numbers N, L, R, and S, the task is to find a permutation of first N natural numbers(1-based indexing) having the sum as S from index L to R. If there are multiple permutations, then print any of them. Otherwise, print -1.
Examples:
Input: N = 6, L = 3, R = 5, S = 8
Output: 3 4 5 2 1 6
Explanation: The output permutation has 5 at index L and 1 at index R. The sum of the numbers from L to R is 8(5+2+1).Input: N = 4, L = 2, R = 3, S = 2
Output: -1
Explanation: There does not exist any permutation in which the sum of numbers from index L to R is S.
Approach: The given problem can be solved by using the Greedy Approach which is based on the observation that suppose X numbers have to be chosen from a permutation of first N natural numbers, so to make the sum as S, let the minimum and maximum sum of X numbers are minSum and maxSum respectively, then:
X = R – L + 1
minSum = X(X + 1)/2
maxSum = X(2*N + 1 – X)/2
Thus, if the given sum S lies in the range [minSum, maxSum], then there exists a permutation such that the sum of all numbers from L to R is S. Otherwise, there does not exist any such permutation. Follow the steps below to solve the problem:
- Define a function possible(int x, int S, int N) and perform the following tasks:
- Initialize the variable minSum as x*(x + 1)/2 and maxSum as (x * ((2*N) – x + 1))/2.
- If S is less than minSum or S is greater than maxSum then return false. Otherwise, return true.
- Initialize the variable, say x as (R – L + 1).
- If the value returned by the function possible(x, S, N) returns false, then print -1 and return from the function.
- Otherwise, initialize a vector v[] to store the numbers present within the given segment.
- Iterate over the range [N, 1] using the variable i and perform the following tasks:
- If S – i is greater than equal to 0 and the function possible(x – 1, S – i, i – 1) returns true then set S as (S – i) decrease the value of x by 1 and push the value of i into the vector v[].
- If S equals 0 then break out of the loop.
- If S does not equal 0 then print -1 and return.
- Initialize a vector, say v1[] to store the numbers which are not present within the given segment.
- Iterate over the range [1, N] using the variable i and initialize a vector iterator it and check if the element i is present in the vector v[] using the find() or not. If it is not present then push it into the vector v1.
- Initialize the variables j and f as 0 to print the results.
- Iterate over the range [1, L) using the variable i and print the value of v1[j], and increase the value of j by 1.
- Iterate over the range [L, R] using the variable i and print the value of v[f], and increase the value of f by 1.
- Iterate over the range [R+1, N] using the variable i and print the value of v1[j], and increase the value of j by 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if sum is possible// with remaining numbersbool possible(int x, int S, int N){ // Stores the minimum sum possible with // x numbers int minSum = (x * (x + 1)) / 2; // Stores the maximum sum possible with // x numbers int maxSum = (x * ((2 * N) - x + 1)) / 2; // If S lies in the range // [minSum, maxSum] if (S < minSum || S > maxSum) { return false; } return true;}// Function to find the resultant// permutationvoid findPermutation(int N, int L, int R, int S){ // Stores the count of numbers // in the given segment int x = R - L + 1; // If the sum is not possible // with numbers in the segment if (!possible(x, S, N)) { // Output -1 cout << -1; return; } else { // Stores the numbers present // within the given segment vector<int> v; // Iterate over the numbers from // 1 to N for (int i = N; i >= 1; --i) { // If (S-i) is a positive non-zero // sum and if it is possible to // obtain (S-i) remaining numbers if ((S - i) >= 0 && possible(x - 1, S - i, i - 1)) { // Update sum S S = S - i; // Update required numbers // in the segment x--; // Push i in vector v v.push_back(i); } // If sum has been obtained if (S == 0) { // Break from the loop break; } } // If sum is not obtained if (S != 0) { // Output -1 cout << -1; return; } // Stores the numbers which are // not present in given segment vector<int> v1; // Loop to check the numbers not // present in the segment for (int i = 1; i <= N; ++i) { // Pointer to check if i is // present in vector v or not vector<int>::iterator it = find(v.begin(), v.end(), i); // If i is not present in v if (it == v.end()) { // Push i in vector v1 v1.push_back(i); } } // Point to the first elements // of v1 and v respectively int j = 0, f = 0; // Print the required permutation for (int i = 1; i < L; ++i) { cout << v1[j] << " "; j++; } for (int i = L; i <= R; ++i) { cout << v[f] << " "; f++; } for (int i = R + 1; i <= N; ++i) { cout << v1[j] << " "; j++; } } return;}// Driver Codeint main(){ int N = 6, L = 3, R = 5, S = 8; findPermutation(N, L, R, S); return 0;} |
Java
import java.util.ArrayList;// Java program for the above approachclass GFG{// Function to check if sum is possible// with remaining numberspublic static boolean possible(int x, int S, int N){ // Stores the minimum sum possible with // x numbers int minSum = (x * (x + 1)) / 2; // Stores the maximum sum possible with // x numbers int maxSum = (x * ((2 * N) - x + 1)) / 2; // If S lies in the range // [minSum, maxSum] if (S < minSum || S > maxSum) { return false; } return true;}// Function to find the resultant// permutationpublic static void findPermutation(int N, int L, int R, int S){ // Stores the count of numbers // in the given segment int x = R - L + 1; // If the sum is not possible // with numbers in the segment if (!possible(x, S, N)) { // Output -1 System.out.print(-1); return; } else { // Stores the numbers present // within the given segment ArrayList<Integer> v = new ArrayList<>(); // Iterate over the numbers from // 1 to N for (int i = N; i >= 1; --i) { // If (S-i) is a positive non-zero // sum and if it is possible to // obtain (S-i) remaining numbers if ((S - i) >= 0 && possible(x - 1, S - i, i - 1)) { // Update sum S S = S - i; // Update required numbers // in the segment x--; // Push i in vector v v.add(i); } // If sum has been obtained if (S == 0) { // Break from the loop break; } } // If sum is not obtained if (S != 0) { // Output -1 System.out.print(-1); return; } // Stores the numbers which are // not present in given segment ArrayList<Integer> v1 = new ArrayList<Integer>(); // Loop to check the numbers not // present in the segment for (int i = 1; i <= N; ++i) { // Pointer to check if i is // present in vector v or not boolean it = v.contains(i); // If i is not present in v if (!it) { // Push i in vector v1 v1.add(i); } } // Point to the first elements // of v1 and v respectively int j = 0, f = 0; // Print the required permutation for (int i = 1; i < L; ++i) { System.out.print(v1.get(j) + " "); j++; } for (int i = L; i <= R; ++i) { System.out.print(v.get(f) + " "); f++; } for (int i = R + 1; i <= N; ++i) { System.out.print(v1.get(j) + " "); j++; } } return;}// Driver Codepublic static void main(String args[]){ int N = 6, L = 3, R = 5, S = 8; findPermutation(N, L, R, S);}}// This code is contributed by saurabh_jaiswal. |
Python3
# python program for the above approach# Function to check if sum is possible# with remaining numbersdef possible(x, S, N): # Stores the minimum sum possible with # x numbers minSum = (x * (x + 1)) // 2 # Stores the maximum sum possible with # x numbers maxSum = (x * ((2 * N) - x + 1)) // 2 # If S lies in the range # [minSum, maxSum] if (S < minSum or S > maxSum): return False return True# Function to find the resultant# permutationdef findPermutation(N, L, R, S): # Stores the count of numbers # in the given segment x = R - L + 1 # If the sum is not possible # with numbers in the segment if (not possible(x, S, N)): # Output -1 print("-1") return else: # Stores the numbers present # within the given segment v = [] # Iterate over the numbers from # 1 to N for i in range(N, 0, -1): # If (S-i) is a positive non-zero # sum and if it is possible to # obtain (S-i) remaining numbers if ((S - i) >= 0 and possible(x - 1, S - i, i - 1)): # Update sum S S = S - i # Update required numbers # in the segment x -= 1 # Push i in vector v v.append(i) # If sum has been obtained if (S == 0): # Break from the loop break # If sum is not obtained if (S != 0): # Output -1 print(-1) return # Stores the numbers which are # not present in given segment v1 = [] # Loop to check the numbers not # present in the segment for i in range(1, N+1): # Pointer to check if i is # present in vector v or not it = i in v # If i is not present in v if (not it): # Push i in vector v1 v1.append(i) # Point to the first elements # of v1 and v respectively j = 0 f = 0 # Print the required permutation for i in range(1, L): print(v1[j], end = " ") j += 1 for i in range(L, R + 1): print(v[f], end = " ") f += 1 for i in range(R + 1, N + 1): print(v1[j], end = " ") j += 1 return# Driver Codeif __name__ == "__main__": N = 6 L = 3 R = 5 S = 8 findPermutation(N, L, R, S) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if sum is possible // with remaining numbers public static bool possible(int x, int S, int N) { // Stores the minimum sum possible with // x numbers int minSum = (x * (x + 1)) / 2; // Stores the maximum sum possible with // x numbers int maxSum = (x * ((2 * N) - x + 1)) / 2; // If S lies in the range // [minSum, maxSum] if (S < minSum || S > maxSum) { return false; } return true; } // Function to find the resultant // permutation public static void findPermutation(int N, int L, int R, int S) { // Stores the count of numbers // in the given segment int x = R - L + 1; // If the sum is not possible // with numbers in the segment if (!possible(x, S, N)) { // Output -1 Console.WriteLine(-1); return; } else { // Stores the numbers present // within the given segment List<int> v = new List<int>(); // Iterate over the numbers from // 1 to N for (int i = N; i >= 1; --i) { // If (S-i) is a positive non-zero // sum and if it is possible to // obtain (S-i) remaining numbers if ((S - i) >= 0 && possible(x - 1, S - i, i - 1)) { // Update sum S S = S - i; // Update required numbers // in the segment x--; // Push i in vector v v.Add(i); } // If sum has been obtained if (S == 0) { // Break from the loop break; } } // If sum is not obtained if (S != 0) { // Output -1 Console.WriteLine(-1); return; } // Stores the numbers which are // not present in given segment List<int> v1 = new List<int>(); // Loop to check the numbers not // present in the segment for (int i = 1; i <= N; ++i) { // Pointer to check if i is // present in vector v or not bool it = v.Contains(i); // If i is not present in v if (!it) { // Push i in vector v1 v1.Add(i); } } // Point to the first elements // of v1 and v respectively int j = 0, f = 0; // Print the required permutation for (int i = 1; i < L; ++i) { Console.Write(v1[j] + " "); j++; } for (int i = L; i <= R; ++i) { Console.Write(v[f] + " "); f++; } for (int i = R + 1; i <= N; ++i) { Console.Write(v1[j] + " "); j++; } } return; } // Driver Code public static void Main() { int N = 6, L = 3, R = 5, S = 8; findPermutation(N, L, R, S); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to check if sum is possible// with remaining numbersfunction possible(x, S, N) { // Stores the minimum sum possible with // x numbers let minSum = (x * (x + 1)) / 2; // Stores the maximum sum possible with // x numbers let maxSum = (x * (2 * N - x + 1)) / 2; // If S lies in the range // [minSum, maxSum] if (S < minSum || S > maxSum) { return false; } return true;}// Function to find the resultant// permutationfunction findPermutation(N, L, R, S) { // Stores the count of numbers // in the given segment let x = R - L + 1; // If the sum is not possible // with numbers in the segment if (!possible(x, S, N)) { // Output -1 document.write(-1); return; } else { // Stores the numbers present // within the given segment let v = []; // Iterate over the numbers from // 1 to N for (let i = N; i >= 1; --i) { // If (S-i) is a positive non-zero // sum and if it is possible to // obtain (S-i) remaining numbers if (S - i >= 0 && possible(x - 1, S - i, i - 1)) { // Update sum S S = S - i; // Update required numbers // in the segment x--; // Push i in vector v v.push(i); } // If sum has been obtained if (S == 0) { // Break from the loop break; } } // If sum is not obtained if (S != 0) { // Output -1 document.write(-1); return; } // Stores the numbers which are // not present in given segment let v1 = []; // Loop to check the numbers not // present in the segment for (let i = 1; i <= N; ++i) { // Pointer to check if i is // present in vector v or not it = v.includes(i); // If i is not present in v if (!it) { // Push i in vector v1 v1.push(i); } } // Point to the first elements // of v1 and v respectively let j = 0, f = 0; // Print the required permutation for (let i = 1; i < L; ++i) { document.write(v1[j] + " "); j++; } for (let i = L; i <= R; ++i) { document.write(v[f] + " "); f++; } for (let i = R + 1; i <= N; ++i) { document.write(v1[j] + " "); j++; } } return;}// Driver Codelet N = 6, L = 3, R = 5, S = 8;findPermutation(N, L, R, S);// This code is contributed by saurabh_jaiswal.</script> |
Output:
3 4 5 2 1 6
Time Complexity: O(N2)
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!
