Cuente todas las sumas únicas posibles de la serie K, K+1, K+2, K+3, K+4, …, K+N

Dado un número N y para cualquier número K para una serie formada como K, K + 1, K + 2, K + 3, K + 4, ……., K + N . La tarea es encontrar el número de sumas únicas que se pueden obtener sumando dos o más enteros de la serie de N + 1 enteros.

Ejemplos:

Entrada: N = 3 
Salida: 10 
Explicación: 
Las posibles combinaciones únicas son: 
(K) + (K + 1) = 2*K + 1 
(K) + (K + 2) = 2*K + 2 
(K) + (K + 3) = 2*K + 3 
(K + 1) + (K + 3) = 2*K + 4 
(K + 2) + (K + 3) = 2*K + 5 
(K) + ( K + 1) + (K + 2) = 3*K + 3 
(K) + (K + 1) + (K + 3) = 3*K + 4 
(K) + (K + 2) + (K + 3) = 3*K + 5 
(K + 1) + (K + 2) + (K + 3) = 3*K + 6 ( 
K) + (K + 1) + (K + 2) + (K + 3) = 4*K + 6 
Entonces, en total, hay 10 formas únicas. 
Entrada: N = 4 
Salida: 20 
Explicación: 
Las posibles combinaciones únicas son 20 en número. 
 

Enfoque: Se deben hacer las siguientes observaciones:

• Dado que K es un número, el único significado que tiene es que dos subconjuntos con diferentes tamaños no pueden tener la misma suma.
• Se puede obtener una suma única desde la suma mínima posible del subconjunto hasta la suma máxima posible del subconjunto que tiene un tamaño como X donde (2 ≤ X ≤ (N + 1)).
   

Por ejemplo: N = 4
La serie es = {K, K + 1, K + 2, K + 3, K + 4}
Para K = 2 , suma_mínima = (K, K + 1) = 2*K + 1
y suma_máxima = (K + 3, K + 4) = 2*K + 7
Las máximas sumas distintas posibles con K = 2 son (suma_máxima – suma_mínima + 1) = (7 – 1 + 1) = 7.

Siga los pasos a continuación para resolver el problema: 

1. Inicialice dos arrays array fsum[] y rsum[] cada una de tamaño N + 1 a 0 .
2. Para cada elemento de las arrays fsum[] y rsum[], actualice fsum[i] con ar[i] + fsum[i – 1] y rsum[i] con ar[i] + fsum[i + 1] .
3. Inicialice una respuesta variable a 1 que almacene el recuento de diferentes sumas posibles de la serie dada.
4. Para cada tamaño de subconjunto posible X , donde (2 ≤ X ≤ (N + 1)), agregue el valor 1 + rsum[n + 1 – k] + fsum[k] a ans .
5. El valor de ans es la respuesta requerida, por lo tanto, devuélvalo.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the unique sum
int count_unique_sum(int n)
{
 
    int i, ar[n + 1], fsum[n + 1];
    int rsum[n + 1], ans = 1;
 
    // Initialize array fsum[] with 0
    memset(fsum, 0, sizeof fsum);
 
    // Initialize array rsum[] with 0
    memset(rsum, 0, sizeof rsum);
 
    for (i = 0; i <= n; i++) {
        ar[i] = i;
    }
 
    // Set fsum[0] as ar[0]
    fsum[0] = ar[0];
 
    // Set rsum[0] as ar[n]
    rsum[n] = ar[n];
 
    // For each i update fsum[i] with
    // ar[i] + fsum[i - 1]
    for (i = 1; i <= n; i++) {
        fsum[i] = ar[i] + fsum[i - 1];
    }
 
    // For each i from n-1, update
    // rsum[i] with ar[i] + fsum[i + 1]
    for (i = n - 1; i >= 0; i--) {
        rsum[i] = ar[i] + rsum[i + 1];
    }
 
    // K represent size of subset as
    // explained above
    for (int k = 2; k <= n; k++) {
 
        // Using above relation
        ans += 1 + rsum[n + 1 - k]
               - fsum[k - 1];
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
int main()
{
    // Given a number N
    int N = 4;
 
    // Function Call
    cout << count_unique_sum(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
   
// Function to count the unique sum
static int count_unique_sum(int n)
{
    int i;
    int ar[] = new int[n + 1];
    int fsum[] = new int[n + 1];
    int rsum[] = new int[n + 1];
    int ans = 1;
   
    // Initialize array fsum[] with 0
    Arrays.fill(fsum, 0);
  
    // Initialize array rsum[] with 0
    Arrays.fill(rsum, 0);
  
    for (i = 0; i <= n; i++)
    {
        ar[i] = i;
    }
  
    // Set fsum[0] as ar[0]
    fsum[0] = ar[0];
  
    // Set rsum[0] as ar[n]
    rsum[n] = ar[n];
  
    // For each i update fsum[i] with
    // ar[i] + fsum[i - 1]
    for (i = 1; i <= n; i++)
    {
        fsum[i] = ar[i] + fsum[i - 1];
    }
  
    // For each i from n-1, update
    // rsum[i] with ar[i] + fsum[i + 1]
    for (i = n - 1; i >= 0; i--)
    {
        rsum[i] = ar[i] + rsum[i + 1];
    }
  
    // K represent size of subset as
    // explained above
    for (int k = 2; k <= n; k++)
    {
  
        // Using above relation
        ans += 1 + rsum[n + 1 - k] -
                     fsum[k - 1];
    }
  
    // Return the result
    return ans;
}
  
// Driver Code
public static void main(String[] args)
{
    // Given a number N
    int N = 4;
  
    // Function Call
    System.out.print(count_unique_sum(N));
}
}
 
// This code is contributed by rock__cool

# Python3 program for the above approach
 
# Function to count the unique sum
def count_unique_sum(n):
 
    ar = [0] * (n + 1)
    fsum = [0] * (n + 1)
    rsum = [0] * (n + 1)
    ans = 1
 
    for i in range(0, n + 1):
        ar[i] = i
     
    # Set fsum[0] as ar[0]
    fsum[0] = ar[0]
 
    # Set rsum[0] as ar[n]
    rsum[n] = ar[n]
 
    # For each i update fsum[i] with
    # ar[i] + fsum[i - 1]
    for i in range(1, n + 1):
        fsum[i] = ar[i] + fsum[i - 1]
 
    # For each i from n-1, update
    # rsum[i] with ar[i] + fsum[i + 1]
    for i in range(n - 1, -1, -1):
        rsum[i] = ar[i] + rsum[i + 1]
     
    # K represent size of subset as
    # explained above
    for k in range(2, n + 1):
 
        # Using above relation
        ans += (1 + rsum[n + 1 - k] -
                    fsum[k - 1])
     
    # Return the result
    return ans
 
# Driver Code
 
# Given a number N
N = 4
 
# Function call
print(count_unique_sum(N))
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
class GFG{
   
// Function to count the unique sum
static int count_unique_sum(int n)
{
    int i;
    int []ar = new int[n + 1];
    int []fsum = new int[n + 1];
    int []rsum = new int[n + 1];
    int ans = 1;
  
    for (i = 0; i <= n; i++)
    {
        ar[i] = i;
    }
  
    // Set fsum[0] as ar[0]
    fsum[0] = ar[0];
  
    // Set rsum[0] as ar[n]
    rsum[n] = ar[n];
  
    // For each i update fsum[i] with
    // ar[i] + fsum[i - 1]
    for (i = 1; i <= n; i++)
    {
        fsum[i] = ar[i] + fsum[i - 1];
    }
  
    // For each i from n-1, update
    // rsum[i] with ar[i] + fsum[i + 1]
    for (i = n - 1; i >= 0; i--)
    {
        rsum[i] = ar[i] + rsum[i + 1];
    }
  
    // K represent size of subset as
    // explained above
    for (int k = 2; k <= n; k++)
    {
  
        // Using above relation
        ans += 1 + rsum[n + 1 - k] -
                   fsum[k - 1];
    }
  
    // Return the result
    return ans;
}
  
// Driver Code
public static void Main(String[] args)
{
    // Given a number N
    int N = 4;
  
    // Function Call
    Console.Write(count_unique_sum(N));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
    // Javascript program for the above approach
     
    // Function to count the unique sum
    function count_unique_sum(n)
    {
 
        let i;
        let ans = 1;
        let ar = new Array(n + 1);
        let fsum = new Array(n + 1);
        let rsum = new Array(n + 1);
 
        // Initialize array fsum[] with 0
        fsum.fill(0);
 
        // Initialize array rsum[] with 0
        rsum.fill(0);
 
        for (i = 0; i <= n; i++) {
            ar[i] = i;
        }
 
        // Set fsum[0] as ar[0]
        fsum[0] = ar[0];
 
        // Set rsum[0] as ar[n]
        rsum[n] = ar[n];
 
        // For each i update fsum[i] with
        // ar[i] + fsum[i - 1]
        for (i = 1; i <= n; i++) {
            fsum[i] = ar[i] + fsum[i - 1];
        }
 
        // For each i from n-1, update
        // rsum[i] with ar[i] + fsum[i + 1]
        for (i = n - 1; i >= 0; i--) {
            rsum[i] = ar[i] + rsum[i + 1];
        }
 
        // K represent size of subset as
        // explained above
        for (let k = 2; k <= n; k++) {
 
            // Using above relation
            ans += 1 + rsum[n + 1 - k]
                   - fsum[k - 1];
        }
 
        // Return the result
        return ans;
    }
     
    // Given a number N
    let N = 4;
   
    // Function Call
    document.write(count_unique_sum(N));
 
//This code is contribute by suresh07.
</script>

20

Complejidad Temporal: O(N) 
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.