# Find sum of non-repeating elements (distinct) elements in an array

Difficulty Level Easy
Frequently asked in Oxigen Wallet
Array Hash Hashing SortingViews 6695

## Problem Statement

Given an integer array, A[] with repeated elements, the “Find sum of non-repeating elements (distinct) elements in an array” problem asks to find the sum of all distinct elements in the array. So, simply add the numbers which are not repeated in the array.

## Example

`A[]={1, 4, 2, 1, 5, 2, 3, 2}`
`11`

Explanation: Non-repeating elements are: 4, 5, 3. So their sum=4+5+3=11.

## Brute force

### Main idea to find sum of non-repeating elements (distinct) elements in an array

For every element, check if there is another element present or not whose value is the same and has an index less than the current index. If there is no such element, add the current element to the answer otherwise skip it.

### Algorithm

```1. Run a loop for I in range 0 to n-1
1. Run a loop for j in range 0 to i
1. If j==i, add A[i].
2. If A[i] is equal to A[j], break out from this loop.
2. Return.```

### Code

#### C++ code

```#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
int n = A.size();
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == i)
{
sum += A[i];
}
if (A[i] == A[j])
{
break;
}
}
}
cout << "Sum of distinct Elements in the array is: " << sum << endl;
return;
}
int main()
{
vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
sumOfDistinctElements(A);
return 0;
}
```
`Sum of distinct Elements in the array is: 15`

#### Java code

```public class Main
{
static void sumOfDistinctElements(int A[])
{
int n = A.length;
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == i)
{
sum += A[i];
}
if (A[i] == A[j])
{
break;
}
}
}
System.out.println("Sum of distinct Elements in the array is: " + sum);
return;
}
public static void main(String[] args) {
int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
sumOfDistinctElements(A);
}
}
```
`Sum of distinct Elements in the array is: 15`

### Complexity Analysis

#### Time complexity

We have two nested loops, each of size n. So the time complexity is O(N^2).

#### Space complexity

We are not taking any extra space so the space complexity is O(1).

## Optimized Approach

### Main idea to find sum of non-repeating elements (distinct) elements in an array

We will maintain a hash table which will store the elements we have already printed. So, we will iterate the array, if we have found an element in the array which is not present in the hash table then we will add that element to the answer and insert it in the hash table, otherwise we will skip that element.

### Algorithm

```1. Declare a hash table.
2. Run a loop for I in range 0 to n-1:
1. If A[i] is not present in the hash table, then add it and insert it in the hash table.
2. If A[i] is not present in the hash table then skip it.
3. Return.```

### Example

Let’s say

`A[]={3, 3, 1, 2 ,1}`

The table on the left side is our input array and purple color points to the current index.

The table on the right is the hash table

### Code

#### C++ code

```#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
int n = A.size();
int sum = 0;
unordered_set<int> hash_table;
for (int i = 0; i < n; i++)
{
if (hash_table.count(A[i]) == 0) //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
{
hash_table.insert(A[i]);
sum += A[i];
}
}
cout << "Sum of distinct Elements in the array is: " << sum << endl;
return;
}
int main()
{
vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
sumOfDistinctElements(A);
return 0;
}
```
`Sum of distinct Elements in the array is: 15`

#### Java code

```import java.util.*;
public class Main
{
static void sumOfDistinctElements(int A[])
{
int n = A.length;
int sum = 0;
HashSet<Integer> hash_table = new HashSet<Integer>();
for (int i = 0; i < n; i++)
{
if (!hash_table.contains(A[i]))
{
sum += A[i];
}
}
System.out.println("Sum of distinct Elements in the array is: " + sum);
return;
}
public static void main(String[] args) {
int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
sumOfDistinctElements(A);
}
}
```
`Sum of distinct Elements in the array is: 15`

### Complexity Analysis

#### Time complexity

We iterate the array only once and the time complexity of insert function in unordered set is O(1), so total time complexity is O(N).

#### Space complexity

We took an extra hash table so our space complexity is O(N).

Translate »