703260. Sum of distinct elements for a limited range
Here is the detailed Markdown blog post for the GeeksforGeeks problem:
Sum of distinct elements for a limited range
Slug: sum-of-distinct-elements-15115 Difficulty: Easy Id: 703260 Topic Tags: Arrays, Data Structures Company Tags: None
Summary
Given an array and a limited range, find the sum of all distinct elements within that range. This problem involves working with arrays and finding unique values.
Detailed Explanation
To solve this problem, we can iterate through the given array and keep track of the distinct elements within the specified range. We'll use a hash set to store these unique elements and then calculate their sum.
Here's a step-by-step breakdown:
- Initialize an empty hash set
distinctElementsto store the distinct elements. - Iterate through the given array:
- For each element
num, check if it falls within the specified range (inclusive). - If it does, add
numto thedistinctElementshash set only if it's not already present (i.e., it's a unique element).
- For each element
- Calculate the sum of all distinct elements by iterating through the
distinctElementshash set and adding up their values.
Time complexity: O(n), where n is the length of the given array, since we're iterating through the array once. Space complexity: O(min(m, n)), where m is the size of the specified range. The space complexity comes from storing the distinct elements in a hash set.
Here's an ASCII art diagram to illustrate the process:
+---------------+
| Given Array |
+---------------+
|
v
+---------------+
| Distinct Elements |
| (Hash Set) |
+---------------+
|
v
+---------------+
| Sum of Unique |
| Elements (Calculated)|
+---------------+
Optimized Solutions
Java
import java.util.*;
public class SumOfDistinctElements {
public static int sumOfDistinct(int[] arr, int low, int high) {
Set<Integer> distinctElements = new HashSet<>();
for (int num : arr) {
if (num >= low && num <= high) {
distinctElements.add(num);
}
}
return distinctElements.stream().mapToInt(i -> i).sum();
}
}