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:
- Brute force: Here, we will use a naive approach with two loops.
- Sorting based: This is an efficient approach which uses the concept of sorting.
- 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
- The outer loop will mark the element if to be selected.
- 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