Horje
Find permutation of numbers upto N with a specific sum in a specific range

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 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 numbers
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
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
        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 Code
int 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 approach
 
class GFG{
 
// Function to check if sum is possible
// with remaining numbers
public 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
// 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
        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 Code
public 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 numbers
def 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
#  permutation
def 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 Code
if __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 approach
using 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 numbers
function 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
// permutation
function 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 Code
 
let 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)

 


 


Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Count of triplets till N whose product is at most N Count of triplets till N whose product is at most N
Count of Unique Direct Path Between N Points On a Plane Count of Unique Direct Path Between N Points On a Plane
Check if elements of given array can be rearranged such that (arr[i] + i*K) % N = i for all values of i in range [0, N-1] Check if elements of given array can be rearranged such that (arr[i] + i*K) % N = i for all values of i in range [0, N-1]
Count of distinct integers belonging to first N terms of at least one of given GPs Count of distinct integers belonging to first N terms of at least one of given GPs
Minimize arithmetic operations to be performed on adjacent elements of given Array to reduce it Minimize arithmetic operations to be performed on adjacent elements of given Array to reduce it

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje