Count all possible unique sum of series K, K+1, K+2, K+3, K+4, …, K+N

0 0 6 minutes read

Given a number N and for any number K for a series formed as K, K + 1, K + 2, K + 3, K + 4, ……., K + N. The task is to find the number of unique sums that can be obtained by adding two or more integers from the series of N + 1 integers.

Examples:

Input: N = 3
Output: 10
Explanation:
The possible unique combinations are:
(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
So in total, there are 10 unique ways.
Input: N = 4
Output: 20
Explanation:
The possible unique combinations are 20 in number.

Approach: The following observations are to be made:

Since K is number the only significance it has is that two subsets with different sizes cannot have the same sum.
A unique sum can be obtained from the minimum possible sum of the subset to the maximum possible sum of subset having size as X where (2 ? X ? (N + 1)).

For Example:N = 4
The Series is = {K, K + 1, K + 2, K + 3, K + 4}
For K = 2, minimum_sum = (K, K + 1) = 2*K + 1
and maximum_sum = (K + 3, K + 4) = 2*K + 7
The maximum distinct sums possible with K = 2 are (maximum_sum – minimum_sum + 1) = (7 – 1 + 1) = 7.

Follow the steps below to solve the problem:

Initialize two arrays array fsum[] and rsum[] each of size N + 1 to 0.
For each element of both the arrays fsum[] and rsum[], update fsum[i] with ar[i] + fsum[i – 1] and rsum[i] with ar[i] + fsum[i + 1].
Initialize a variable ans to 1 that stores the count of different possible sums of the given series.
For each possible subset size X, where (2 ? X ? (N + 1)), add the value 1 + rsum[n + 1 – k] + fsum[k] to ans.
The value of ans is the required answer hence return it.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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

Javascript

<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 contributed by suresh07.
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N), since N extra space has been taken.

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 zambiatek!