Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Pseudocode
2.3.
Implementation in C++
2.4.
Implementation in Python
2.4.1.
Complexity Analysis
3.
Optimized Approach 1
3.1.
Steps of Algorithm
3.2.
Pseudocode
3.3.
Implementation in C++
3.3.1.
 
3.4.
Implementation in Python
3.4.1.
Complexity Analysis
4.
Optimized Approach 2
4.1.
Pseudocode
4.2.
Implementation in C++
4.3.
Implementation in Python
4.3.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What are the different sorting algorithms that can be used in the above approach?
5.2.
What is hashing?
5.3.
What is the difference between a HashSet and a set?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find the sum of all the distinct elements in an array

Author Akshit Mehra
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing the problem of finding the sum of all distinct elements in an array. Here, we will discuss 3 approaches:

  1. Brute force:  Here, we will use a naive approach with two loops.
  2. Sorting based: This is an efficient approach which uses the concept of sorting.
  3. Hashing based: Here, we use the concept of hashing. In this approach, the time complexity is the best among the 3, but has a space complexity of O(n)

 

Hashing: Hashing is a method of employing a hash function to map a huge amount of arbitrary data to tabular indices. It's a way of displaying dictionaries for enormous datasets. It enables constant-time lookups, updating, and retrieval operations, i.e. (1).

We hope you enjoy learning the concept in the provided blog.

Problem Statement

The problem above states that given an array of elements, we have to find and calculate the sum of all the distinct elements (non-repetitive) in the array. For further clarification, refer to the below example.

Sample Example

Input 1:

arr[] = {1, 2, 3, 3, 3, 2, 1}

 

Output 1:

6

 

We take 1, 2, and 3 for the sum in the above example, as these are the only distinct elements.

Input 2

arr[] = {10, 12, 11, 12, 10, 21}

 

Output 2: 

54

 

As in the above array, 10,12,11,21 are the distinct elements, therefore we take their sum only.

Brute Force Approach

A brute force approach is to run two nested Loops. 

Steps of Algorithm

  1. The outer loop will mark the element if to be selected.
  2. The inner loop will run and check if the marked element is present on the left side of it. If not, it will select the element and add it to the sum. Else, it will continue.

Pseudocode

For i = 0 to n:
	Bool flag = true
	For j = 0 to i-1:
		If arr[j] is equal to arr[i]:
			Flag = false
			Break
	If flag is equal true:
		sum = sum + arr[i]

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  

    //Below is the defined array.
    int arr[] = {1,3,2,3,2,1};
    int sum = 0;


    // Defining the size of the array.
    int n = sizeof(arr)/sizeof(int);


    //Iterating the first loop for checking for elements between 1 to n
    for(int i = 0;i<n;i+=1){
       //Using a boolean variable to check if an element is repeated.
        bool flag = true;
       
        //Iterating the second loop for checking if this element exists on the left side.
        for(int j = 0;j<i;j+=1){
            if(arr[j] == arr[i]){
                flag=false;
                break;
            }
        } 
        // If the element is not repeated, we add it to the sum.
        if(flag){
            sum+=arr[i];
        }
    }
    cout<<"Sum is: "<<sum;
 
}  
int main()
{
    solve();
    return 0;
}

 

Output

6

 

Implementation in Python

def solve(arr, n):
    sum = 0
   
    #Iterating the first loop for checking for elements between 1 to n
    for i in range(n):
        #Using a boolean variable to check if an element is repeated.
        flag = True
        
        #Iterating the second loop for checking if this element exists on the left side.
        for j in range(i):
            if arr[j] == arr[i]:
                flag = False
                break
        
        #if the element is not repeated, we add it to the sum.
        if flag:
           sum = sum + arr[i]
    print(sum)


#Below is the defined array.
arr = [1,2,3,3,2,1]
#Defining the size of the array.
n = len(arr)
solve(arr,n)

 

Output: 

6

 

Complexity Analysis

Time complexity: O(n2)

The time complexity for the above code is n2 as we have two nested loops applied.

Space complexity: O(1)

As in the above approach to solve the problem, we haven’t used any extra space for solving it. Therefore, the space complexity is O(1), i.e. constant.

Read More - Time Complexity of Sorting Algorithms and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach 1

An efficient approach for solving the above problem is to use sorting techniques. Here, we first sort the whole array and then look for the distinct elements in the array. For sorting, we can use Merge sort. 

Steps of Algorithm

  1. First, we sort the array.
  2. Now, we start traversing the array, If the next element is not equal to the current element, then we add it to our sum. This is so as our array is already sorted, therefore, the elements would be occurring in an increasing manner.
  3. If the next element is equal to the current element, then we ignore the current element as it is repeated.
  4. We anyway add the last element, In either case if it gets repeated, it won't be added until its last occurrence. If it doesn't get repeated, we will anyway add it.

Pseudocode

sort(arr, arr + n)
sum = 0
For i = 0 to n-1:
	If arr[i] != arr[i+1]:
	sum = sum + arr[i]
sum = sum + arr[n-1]

Implementation in C++

#include "bits/stdc++.h"
using namespace std;
void solve()
{  
    //Below is the defined array.
    int arr[] = {1,3,2,3,2,1};
    int sum = 0;

    // Defining the size of the array.
    int n = sizeof(arr)/sizeof(int);

    //Sorting the array in non-decreasing form.
    sort(arr, arr+n);
    //Now, we traverse the array to check if an element repeats. We do this by checking consecutive elements. As we had already sorted the array, the repeated elements will occur consecutively.
    for(int i = 0;i<n-1;i+=1){
        if(arr[i]!=arr[i+1]){
            sum+=arr[i];
        }
    }
   //Adding the last element to the sum.
    sum+=arr[n-1];
    cout <<sum;
 
}  
int main()
{
    solve();
    return 0;
}

 

Output: 

6

 

Implementation in Python

def solve(arr, n):
    sum = 0
    // Sorting the array
    arr.sort()


      #Now, we traverse the array to check if an element repeats. We do this by checking       
      #consecutive elements. As we had already sorted the array, the repeated elements will   
      #occur consecutively.
    for i in range(n-1):
        if arr[i]!=arr[i+1]:
            sum+=arr[i]
    #Adding the last element to the sum.
    sum+=arr[n-1]
    print(sum)


arr = [1,2,3,3,2,1]
n = len(arr)
solve(arr,n)

 

Output: 

6

 

Complexity Analysis

Time complexity: O(nlog(n))

The Time complexity for the above code can be broken down into two parts:

  1. O(nlog(n)) : For sorting the array.
  2. O(n): For finding the distinct elements in the array.

 

Therefore, final Time complexity is O(n) + O(nlog(n)) which comes out to be O(nlog(n)).

Space complexity: O(1)

Again, in the above approach, we haven’t used any extra space but have only sorted the original array provided to us. Therefore, the space complexity for above code is O(1).

Also Read - Selection Sort in C

Optimized Approach 2

A more efficient approach here includes the use of hashing. We can use unordered_set in C++ or HashSet in Java to store the elements. As hashing will only store distinct elements, we can then get the required sum by just iterating over the HashSet/unordered set.

Pseudocode

hashset st;
for i = 0 to n:
	st.insert(arr[i])
sum = 0
for i in st:
	sum = sum + i

Implementation in C++

typedef long long ll;
typedef long double ld;
#include "bits/stdc++.h"
using namespace std;
void solve()
{  
     //Below is the defined array.
    int arr[] = {1,3,2,3,2,1};
    int sum = 0;


    // Defining the size of the array.
    int n = sizeof(arr)/sizeof(int);


    //Defining a hash-set for hashing purposes.
    unordered_set<int>st;


    //Inserting all distinct elements in the hash-set.
    for(int i = 0;i<n;i+=1){
        st.insert(arr[i]);
    }
    int sum = 0;


    //As the hash-set only contains distinct elements, we simply add all the elements in the hash-set.
    for(auto i: st){
        sum+=i;
    }
    cout<<sum<<'\n';
}  
int main()
{
    solve();
    return 0;
}

 

Output: 

6

 

Implementation in Python

def solve(arr, n):
    st = set()
    # Hashset to store all element
    # of array
    
    sum = 0
    for i in range(n):
        if arr[i] not in st:
            st.add(arr[i])


#As the hash-set only contains distinct elements, we simply add all the elements in the hash-set.
    for i in st:
        sum = sum + i
    print(sum)


arr = [1,2,3,3,2,1]
n = len(arr)
solve(arr,n)

 

Output: 

6

 

Complexity Analysis

Time complexity: O(n)

In the above code, we run two loops, both of O(n) time complexity. Thus, the overall time complexity becomes O(n)

Space complexity: O(n)

The space complexity is O(n) as if we have an array with all the elements as distinct, then our HashSet will effectively have all the n elements in it. Therefore, the worst-case complexity here is O(n).

Frequently Asked Questions

What are the different sorting algorithms that can be used in the above approach?

Apart from Merge sort, we can use Quicksort in the above problem, as it also gives O(nlog(n)) as its average time complexity. But, if we’ve used Bubble sort, Insertion sort, or selection sort, our time complexity would have become O(n2).

What is hashing?

Hashing is a method of employing a hash function to map a huge amount of arbitrary data to tabular indices. It's a way of displaying dictionaries for enormous datasets. It enables constant-time lookups, updating, and retrieval operations, i.e. (1).

What is the difference between a HashSet and a set?

A hash set is implemented using a hash table, which has O(1) operations largely, whereas a set is implemented using an O(log n) tree (AVL, red-black, etc.) with sorted operations.

Conclusion

This article discussed the problem of finding the sum of all distinct elements belonging to an array. Once you are done with this, you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, Javascript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview undle and interview experiences for placement preparations.

We hope that this blog has helped you increase your knowledge regarding such DSA problem, and if you liked this blog, check other links. Do upvote our blog to help other ninjas grow. Happy Coding!"

Live masterclass