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 sumint 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 Codeint main(){ // Given a number N int N = 4; // Function Call cout << count_unique_sum(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to count the unique sumstatic 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 Codepublic 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 sumdef 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 NN = 4# Function callprint(count_unique_sum(N))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the unique sumstatic 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 Codepublic 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
20
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
