Given three integers N, L, and R. The task is to count distinct sums formed by using N numbers from the range [L, R], where any number can be taken infinite times.
Examples:
Input: N = 2, L = 1, R = 3
Output: 5
Explanation: Generating all distinct combinations of 2 numbers taken from the range [1, 3]
{1, 1} => sum = 2
{1, 2} => sum = 3
{1, 3} => sum = 4
{2, 2} => sum = 4
{2, 3} => sum = 5
{3, 3} => sum = 6
Therefore, there are 5 (2, 3, 4, 5, 6) different sums possible with 2 numbers taken from range [1, 3].Input: N = 3, L = 1, R = 9
Output: 10
Naïve Approach: The simplest approach to solve the given problem is to generate all possible combinations of N numbers from the range [L, R] and then count the total distinct sums formed by those combinations.
Time Complexity: O((R – L)N)
Auxiliary Space: O(1)
Efficient Approach: The given problem can be solved by some observation and by the use of some math. Here minimum and maximum numbers that can be used are L and R respectively. So, the minimum and maximum possible sum that can be formed are L*N (all N numbers are L) and R*N (all N numbers are R) respectively, Similarly, all other sums in between this range can also be formed. Follow the steps below to solve the given problem.
- Initialize a variable say, minSum = L*N, to store the minimum possible sum.
- Initialize a variable say, maxSum = R*N, to store the maximum possible sum.
- The final answer is the total numbers in the range [minSum, maxSum] i.e., (maxSum – minSum + 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 find total number of // different sums of N numbers in // the range [L, R] int countDistinctSums(int N, int L, int R) { // To store minimum possible sum with // N numbers with all as L int minSum = L * N; // To store maximum possible sum with // N numbers with all as R int maxSum = R * N; // All other numbers in between maxSum // and minSum can also be formed so numbers // in this range is the final answer return maxSum - minSum + 1; } // Driver Code int main() { int N = 2, L = 1, R = 3; cout << countDistinctSums(N, L, R); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find total number of // different sums of N numbers in // the range [L, R] static int countDistinctSums(int N, int L, int R) { // To store minimum possible sum with // N numbers with all as L int minSum = L * N; // To store maximum possible sum with // N numbers with all as R int maxSum = R * N; // All other numbers in between maxSum // and minSum can also be formed so numbers // in this range is the final answer return maxSum - minSum + 1; } // Driver Code public static void main(String[] args) { int N = 2, L = 1, R = 3; System.out.print(countDistinctSums(N, L, R)); } } // This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach # Function to find total number of # different sums of N numbers in # the range [L, R] def countDistinctSums(N, L, R): # To store minimum possible sum with # N numbers with all as L minSum = L * N # To store maximum possible sum with # N numbers with all as R maxSum = R * N # All other numbers in between maxSum # and minSum can also be formed so numbers # in this range is the final answer return maxSum - minSum + 1 # Driver Code if __name__ == "__main__": N = 2 L = 1 R = 3 print(countDistinctSums(N, L, R)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find total number of // different sums of N numbers in // the range [L, R] static int countDistinctSums(int N, int L, int R) { // To store minimum possible sum with // N numbers with all as L int minSum = L * N; // To store maximum possible sum with // N numbers with all as R int maxSum = R * N; // All other numbers in between maxSum // and minSum can also be formed so numbers // in this range is the final answer return maxSum - minSum + 1; } // Driver Code public static void Main() { int N = 2, L = 1, R = 3; Console.Write(countDistinctSums(N, L, R)); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find total number of // different sums of N numbers in // the range [L, R] function countDistinctSums(N, L, R) { // To store minimum possible sum with // N numbers with all as L let minSum = L * N; // To store maximum possible sum with // N numbers with all as R let maxSum = R * N; // All other numbers in between maxSum // and minSum can also be formed so numbers // in this range is the final answer return maxSum - minSum + 1; } // Driver Code let N = 2, L = 1, R = 3; document.write(countDistinctSums(N, L, R)); // This code is contributed by Potta Lokesh </script> |
5
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
