Encuentre K enteros positivos que no excedan N y que tengan una suma S

Dados tres enteros positivos S, K y N , la tarea es encontrar K enteros positivos distintos, que no excedan N y que tengan una suma igual a S. Si no es posible encontrar K enteros positivos, imprima -1 .

Ejemplos:

Entrada: S = 15, K = 4, N = 8
Salida: 1 2 4 8
Explicación:
Un conjunto posible de K tales números es {1, 2, 3, 4} (Puesto que, 1 + 2 + 4 + 8 =15 ).
Otro conjunto posible de números K son {2, 3, 4, 6}, {1, 3, 4, 7}, etc.

Entrada: S = 14, K = 5, N = 6
Salida: -1

Enfoque: siga los pasos a continuación para resolver el problema:

• Si N es menor que K , imprima -1 .
• Si S es menor que la suma de los primeros K números naturales , es decir (1 + 2 + … + K) o si S es mayor que la suma de los últimos K números naturales , es decir, de N a N – K + 1 , entonces imprima – 1 .
• Itere desde 1 y siga agregando todos los números naturales encontrados en una variable, digamos s1 , mientras que s1 ≤ S. Inserte todos los elementos encontrados en una array, digamos nums[] .
• Extraiga K – 1 elementos de nums[] y guárdelos en otra array, diga answer .
• El K ^-ésimo elemento en el arreglo answer[] será (s1 – s2) , donde s2 es la suma de los K – 1 elementos presentes en el arreglo answer[] .
• Recorra la array answer[] al revés y reduzca todos los elementos de la array a menos o igual a N .

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation
// for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to represent S as
// the sum of K positive integers
// less than or equal to N
void solve(int S, int K, int N)
{
    if (K > N) {
        cout << "-1" << endl;
        return;
    }
 
    int max_sum = 0, min_sum = 0;
 
    for (int i = 1; i <= K; i++) {
        min_sum += i;
        max_sum += N - i + 1;
    }
 
    // If S can cannot be represented
    // as sum of K integers
    if (S < min_sum || S > max_sum) {
        cout << "-1" << endl;
        return;
    }
 
    int s1 = 0;
 
    vector<int> nums;
 
    for (int i = 1; i <= N; i++) {
 
        // If sum of first i natural
        // numbers exceeds S
        if (s1 > S)
            break;
 
        s1 += i;
 
        // Insert i into nums[]
        nums.push_back(i);
    }
 
    vector<int> answer;
    int s2 = 0;
 
    // Insert first K - 1 positive
    // numbers into answer[]
    for (int i = 0; i < K - 1; i++) {
        answer.push_back(nums[i]);
        s2 += nums[i];
    }
 
    // Insert the K-th number
    answer.push_back(S - s2);
 
    int Max = N;
 
    // Traverse the array answer[]
    for (int i = answer.size() - 1; i >= 0; i--) {
 
        // If current element exceeds N
        if (answer[i] > Max) {
 
            int extra = answer[i] - Max;
 
            // Add the extra value to
            // the previous element
            if (i - 1 >= 0)
                answer[i - 1] += extra;
 
            // Reduce current element to N
            answer[i] = Max;
 
            Max--;
        }
 
        else
            break;
    }
 
    // Printing the K numbers
    for (auto x : answer)
        cout << x << " ";
 
    cout << endl;
}
 
// Driver Code
int main()
{
    int S = 15, K = 4, N = 8;
    solve(S, K, N);
 
    return 0;
}

// Java implementation
// for the above approach
import java.util.Vector;
 
class GFG{
 
// Function to represent S as
// the sum of K positive integers
// less than or equal to N
static void solve(int S, int K, int N)
{
    if (K > N)
    {
        System.out.println("-1");
        return;
    }
 
    int max_sum = 0, min_sum = 0;
 
    for(int i = 1; i <= K; i++)
    {
        min_sum += i;
        max_sum += N - i + 1;
    }
 
    // If S can cannot be represented
    // as sum of K integers
    if (S < min_sum || S > max_sum)
    {
        System.out.println("-1");
        return;
    }
 
    int s1 = 0;
 
    Vector<Integer> nums = new Vector<>();
 
    for(int i = 1; i <= N; i++)
    {
         
        // If sum of first i natural
        // numbers exceeds S
        if (s1 > S)
            break;
 
        s1 += i;
 
        // Insert i into nums[]
        nums.add(i);
    }
    Vector<Integer> answer = new Vector<>();
    int s2 = 0;
 
    // Insert first K - 1 positive
    // numbers into answer[]
    for(int i = 0; i < K - 1; i++)
    {
        answer.add(nums.get(i));
        s2 += nums.get(i);
    }
 
    // Insert the K-th number
    answer.add(S - s2);
 
    int Max = N;
 
    // Traverse the array answer[]
    for(int i = answer.size() - 1;
            i >= 0; i--)
    {
         
        // If current element exceeds N
        if (answer.get(i) > Max)
        {
            int extra = answer.get(i) - Max;
 
            // Add the extra value to
            // the previous element
            if (i - 1 >= 0)
                answer.set(i - 1,
                answer.get(i - 1) + extra);
 
            // Reduce current element to N
            answer.set(i, Max);
 
            Max--;
        }
        else
            break;
    }
 
    // Printing the K numbers
    for(int x : answer)
        System.out.print(x + " ");
 
    System.out.println();
}
 
// Driver code
public static void main(String[] args)
{
    int S = 15, K = 4, N = 8;
     
    solve(S, K, N);
}
}
 
// This code is contributed by abhinavjain194

# Python3 implementation
# for the above approach
 
# Function to represent S as
# the sum of K positive integers
# less than or equal to N
def solve(S, K, N):
    if (K > N):
        print("-1")
        return
 
    max_sum, min_sum = 0, 0
 
    for i in range(K + 1):
        min_sum += i
        max_sum += N - i + 1
 
    # If S can cannot be represented
    # as sum of K integers
    if (S < min_sum or S > max_sum):
        print("-1")
        return
 
    s1 = 0
 
    nums = []
 
    for i in range(1, N + 1):
 
        # If sum of first i natural
        # numbers exceeds S
        if (s1 > S):
            break
 
        s1 += i
 
        # Insert i into nums[]
        nums.append(i)
 
    answer = []
    s2 = 0
 
    # Insert first K - 1 positive
    # numbers into answer[]
    for i in range(K - 1):
        answer.append(nums[i])
        s2 += nums[i]
 
    # Insert the K-th number
    answer.append(S - s2)
 
    Max = N
 
    # Traverse the array answer[]
    for i in range(len(answer)-1,-1,-1):
 
        # If current element exceeds N
        if (answer[i] > Max):
 
            extra = answer[i] - Max
 
            # Add the extra value to
            # the previous element
            if (i - 1 >= 0):
                answer[i - 1] += extra
 
            # Reduce current element to N
            answer[i] = Max
 
            Max -= 1
        else:
            break
 
    # Printing the K numbers
    for x in answer:
        print(x, end = " ")
 
 
# Driver Code
if __name__ == '__main__':
    S,K,N = 15, 4, 8
    solve(S, K, N)
 
# This code is contributed by mohit kumar 29.

// C# implementation
// for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to represent S as
// the sum of K positive integers
// less than or equal to N
static void solve(int S, int K, int N)
{
    if (K > N)
    {
        Console.WriteLine("-1");
        return;
    }
 
    int max_sum = 0, min_sum = 0;
 
    for(int i = 1; i <= K; i++)
    {
        min_sum += i;
        max_sum += N - i + 1;
    }
 
    // If S can cannot be represented
    // as sum of K integers
    if (S < min_sum || S > max_sum)
    {
        Console.WriteLine("-1");
        return;
    }
 
    int s1 = 0;
    List<int> nums = new List<int>();
 
    for(int i = 1; i <= N; i++)
    {
         
        // If sum of first i natural
        // numbers exceeds S
        if (s1 > S)
            break;
 
        s1 += i;
 
        // Insert i into nums[]
        nums.Add(i);
    }
 
    List<int> answer = new List<int>();
    int s2 = 0;
 
    // Insert first K - 1 positive
    // numbers into answer[]
    for(int i = 0; i < K - 1; i++)
    {
        answer.Add(nums[i]);
        s2 += nums[i];
    }
 
    // Insert the K-th number
    answer.Add(S - s2);
 
    int Max = N;
 
    // Traverse the array answer[]
    for(int i = answer.Count - 1; i >= 0; i--)
    {
         
        // If current element exceeds N
        if (answer[i] > Max)
        {
            int extra = answer[i] - Max;
 
            // Add the extra value to
            // the previous element
            if (i - 1 >= 0)
                answer[i - 1] += extra;
 
            // Reduce current element to N
            answer[i] = Max;
 
            Max--;
        }
        else
            break;
    }
 
    // Printing the K numbers
    foreach(int x in answer)
        Console.Write(x + " ");
 
    Console.WriteLine();
}
 
// Driver Code
public static void Main()
{
    int S = 15, K = 4, N = 8;
    solve(S, K, N);
}
}
 
// This code is contributed by ukasp

<script>
 
// Javascript implementation
// for the above approach
 
// Function to represent S as
// the sum of K positive integers
// less than or equal to N
function solve(S, K, N)
{
    if (K > N)
    {
        document.write("-1");
        return;
    }
  
    let max_sum = 0, min_sum = 0;
  
    for(let i = 1; i <= K; i++)
    {
        min_sum += i;
        max_sum += N - i + 1;
    }
  
    // If S can cannot be represented
    // as sum of K integers
    if (S < min_sum || S > max_sum)
    {
        document.write("-1");
        return;
    }
  
    let s1 = 0;
    let nums = [];
  
    for(let i = 1; i <= N; i++)
    {
          
        // If sum of first i natural
        // numbers exceeds S
        if (s1 > S)
            break;
  
        s1 += i;
  
        // Insert i into nums[]
        nums.push(i);
    }
  
    let answer = [];
    let s2 = 0;
  
    // Insert first K - 1 positive
    // numbers into answer[]
    for(let i = 0; i < K - 1; i++)
    {
        answer.push(nums[i]);
        s2 += nums[i];
    }
  
    // Insert the K-th number
    answer.push(S - s2);
  
    let Max = N;
  
    // Traverse the array answer[]
    for(let i = answer.length - 1; i >= 0; i--)
    {
          
        // If current element exceeds N
        if (answer[i] > Max)
        {
            let extra = answer[i] - Max;
  
            // Add the extra value to
            // the previous element
            if (i - 1 >= 0)
                answer[i - 1] += extra;
  
            // Reduce current element to N
            answer[i] = Max;
  
            Max--;
        }
        else
            break;
    }
  
    // Printing the K numbers
    for(let x in answer)
        document.write(answer[x] + " ");
  
    document.write("<br/>");
}
  
 
// Driver Code
     
    let S = 15, K = 4, N = 8;
    solve(S, K, N);
  
 // This code is contributed by susmitakundugoaldanga.
</script>

1 2 4 8

Complejidad temporal: O(N)
Espacio auxiliar: O(N)