Given two positive integers L and R ( where L ? R ), the task is to count the number of distinct integers that can be obtained by adding any pair of integers from the range [L, R].
Examples:
Input: L = 3, R = 5
Output: 11
Explanation: All possible distinct sum of pairs are as follows:
- (3, 3). Sum = 6.
- (3, 4). Sum = 7.
- (3, 5). Sum = 8.
- (4, 5). Sum = 9.
- (5, 5). Sum = 10.
Therefore, the count of distinct sums is 5.
Input: L = 12, R = 14
Output: 5
Naive Approach: The simplest approach to solve the given problem is to find the sum of all possible pairs of numbers from the range [L, R] and print the count of all distinct sums obtained.
Time Complexity: O((L – R)2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
- Since, the given range [L, R] is continuous, the range of numbers obtained by adding will also be continuous.
- The minimum and maximum sum of pairs from the range are given by 2 * L and 2 * R respectively.
- Therefore, the count distinct sum of pairs is given by (2 * R – 2 * L + 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 count distinct sum of// pairs possible from the range [L, R]int distIntegers(int L, int R){ // Return the count of // distinct sum of pairs return 2 * R - 2 * L + 1;}// Driver Codeint main(){ int L = 3, R = 8; cout << distIntegers(L, R); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to count distinct sum of// pairs possible from the range [L, R]static int distIntegers(int L, int R){ // Return the count of // distinct sum of pairs return 2 * R - 2 * L + 1;} // Driver Codepublic static void main (String[] args) { int L = 3, R = 8; System.out.println(distIntegers(L, R));}}// This code is contributed by rag2127 |
Python3
# Python3 program for the above approach# Function to count distinct sum of# pairs possible from the range [L, R]def distIntegers(L, R): # Return the count of # distinct sum of pairs return 2 * R - 2 * L + 1# Driver Codeif __name__ == '__main__': L, R = 3, 8 print (distIntegers(L, R))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to count distinct sum of// pairs possible from the range [L, R]static int distIntegers(int L, int R){ // Return the count of // distinct sum of pairs return 2 * R - 2 * L + 1;}// Driver Codestatic public void Main(){ int L = 3, R = 8; Console.Write(distIntegers(L, R));}}// This code is contributed by avijitmondal1998 |
Javascript
<script> // Function to count distinct sum of // pairs possible from the range [L, R] function distIntegers(L,R) { // Return the count of // distinct sum of pairs return 2 * R - 2 * L + 1; } // Driver Code let L = 3, R = 8; document.write(distIntegers(L, R)); // This code is contributed by avanitrachhadiya2155 </script> |
11
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!
