CODEWITHSUNDEEP
algorithmdata-structuressegment-tree
nil96
nil96

Reputation: 310

Sum of distinct element in a range

Consider a array (0 based index) i have to find the sum of distinct element of all possible range[i,n] where 0< i < n

Example:

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3

O(n^2) solution is one possible solution and i have read persistent segment tree can also do this though i can't find good tutorial.

Can it be solved in less than O(N^2) time?

If someone points persistent segment tree please explain or provide some good link?

Upvotes: 3

Views: 744

Answers (3)

Pradeep Mishra
Pradeep Mishra

Reputation: 1

There are multiple ways to solve this.

  1. sort the array by Arrays.sort();

  2. Using set

    long sumOfDistinct(long arr[], int N)
{
     int size = arr.length;
     HashSet<Long> unique = new HashSet<Long>(); 
     long sum = 0;
     for(int i=0;i<size;i++){
             if(!unique.contains(arr[i])){
                 sum = sum + arr[i];
                 unique.add(arr[i]);
             }
     }

     return sum;
 }

Upvotes: 0

Diane M
Diane M

Reputation: 1512

Slice the array (O(n)), then use a set and add values to the set.

In python3.x code, edited after a comment:

array = [1, 2, 1, 3, 5]
range_sum = 0
total_sum = 0
valueset = set ()
for val in reversed(array):
    if val not in valueset :
        valueset.add (val)
        range_sum += val
    total_sum += range_sum

print (total_sum)

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

This can be done in O(n) with a simple dynamic programming algorithm.

Start from the back of the array, and use a hash-based container to store the numbers that you have already encountered. The value of the last element, i.e. sum_range[n-1] is set to arr[n-1]. After that, values of sum_range[i] should be computed as follows:

  • If arr[i] is not in the set of seen numbers, sum_range[i] = sum_range[i+1]+arr[i]
  • Otherwise, sum_range[i] = sum_range[i+1]

Since the cost of checking a hash container for a value is O(1) and the cost of adding an item to hash container is amortized O(1) for n items, the overall cost of this algorithm is O(n).

Compared to O(n2) algorithm that uses O(1) space, this algorithm uses additional O(n) space for the hash container.

Upvotes: 5

Related Questions