Find sum of non-repeating (distinct) elements in an array
Examples:
Input : arr[] = {12, 10, 9, 45, 2, 10, 10, 45,10}; Output : 78 Here we take 12, 10, 9, 45, 2 for sum because it's distinct elements Input : arr[] = {1, 10, 9, 4, 2, 10, 10, 45 , 4}; Output : 71
A Simple Solution is to use two nested loops. The outer loop picks an element one by one starting from the leftmost element. The inner loop checks if the element is present enabled right side of it. If present, then ignores the element.
Steps that were to follow the above approach:
- Make a variable sum and initialize it with 0. It is the variable that will contain the final answer
- Now traverse the input array
- While traversing the an array pick an element and check all elements to its right by running an inner loop.
- If we get any element with the same value when that element then stop the inner loop
- If any element exists to the right of that element that has the same value then it is ok else add the value of that element to the sum.
Code to implement the above approach:
Python3
# Find the sum of all non-repeated elements # in an an array def findSum(arr): # Initialize a variable with 0 to contain final answer sum = 0 # Traverse the input an array for i in range(len(arr)): j = i + 1 while j < len(arr): # If any element present enabled the right of arr[i] that has # same value when arr[i] then break the loop if arr[j] == arr[i]: break j += 1 # If no such element exists then add this element's value into sum if j == len(arr): sum += arr[i] # Finally return the answer return sum # Driver code arr = [1, 2, 3, 1, 1, 4, 5, 6] print(findSum(arr)) |
21
A Better Solution of this problem is that using sorting technique we firstly sort all elements of an array in ascending order and find one by one distinct elements in array.
Implementation:
Python3
# Python3 Find the sum of all non-repeated # elements in an array # Find the sum of all non-repeated elements # in an an array def findSum(arr, n): # sort all elements of an array arr.sort() sum = arr[0] for i in range(0,n-1): if (arr[i] != arr[i+1]): sum = sum + arr[i+1] return sum # Driver code def main(): arr= [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(findSum(arr, n)) if __name__ == '__main__': main() |
21
An Efficient solution to this problem is that using unordered_set we run a single for loop and in which the value comes the first time it’s an add-in sum variable and stored in a hash table that for the next time we do not use this value.
Implementation:
Python3
# Python3 Find the sum of all # non- repeated elements in an array # Find the sum of all non-repeated # elements in an an array def findSum(arr, n): s = set() sum = 0 # Hash to store all element # of an array for i in range(n): if arr[i] not in s: s.add(arr[i]) for i in s: sum = sum + i return sum # Driver code arr = [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(findSum(arr, n)) # This code is contributed by Shrikant13 |
21
Approach for python:
- Calculate the frequencies using Counter() function
- Convert the frequency keys to the list.
- Calculate the sum of the list.
Below is the implementation of the above approach.
Python3
# Python program for the above approach from collections import Counter # Function to return the sum of distinct elements def sumOfElements(arr, n): # Counter function/method is have used to # calculate frequency of elements of an array freq = Counter(arr) # Converting keys of freq dictionary to list lis = list(freq.keys()) # Return sum of list return sum(lis) # Driver code if __name__ == "__main__": arr = [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(sumOfElements(arr, n)) |
21