703055. Sum of distinct elements
Sum of distinct elements
Summary
Given an array of integers, find the sum of all distinct elements in it. This problem is about arrays and data structures.
Detailed Explanation
The key concept involved here is finding distinct elements in an array. We can achieve this by using a HashSet or a set data structure to store unique elements. Then we simply iterate over the original array, adding each element to our sum if it's not already present in the set.
Here's a step-by-step breakdown of the solution:
- Initialize an empty HashSet
distinctSetand a variablesumto 0. - Iterate over the input array:
- For each element, check if it's not already present in
distinctSet. - If it's not, add it to
distinctSetand updatesumby adding the element.
- For each element, check if it's not already present in
- Return the calculated sum.
Time complexity: O(n), where n is the size of the input array. This is because we're making a single pass over the array and performing constant-time operations inside the loop.
Space complexity: O(n) as well, since in the worst case (when all elements are unique), we'll store every element in the distinctSet.
Optimized Solutions
Java
public int sumDistinct(int[] arr) {
Set<Integer> distinctSet = new HashSet<>();
int sum = 0;
for (int num : arr) {
if (!distinctSet.contains(num)) {
distinctSet.add(num);
sum += num;
}
}
return sum;
}