Teaching Kids Programming – Sum of Unique Elements

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array. Return the sum of all the unique elements of nums.

Example 1:
Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:
Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:
Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100

Hints:
Use a dictionary to count the frequency of each number.

Sum of Unique Elements

We can use the sum and count:

1
2
3

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        return sum([i for i in nums if nums.count(i) == 1])

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        return sum([i for i in nums if nums.count(i) == 1])

The count takes O(N) and therefore the above algorithm takes O(N^2) quadratic complexity. The unroll-ed version is:

1
2
3
4
5
6
7

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        ans = 0
        for i in nums:
            if nums.count(i) == 1:
                ans += i
        return ans

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        ans = 0
        for i in nums:
            if nums.count(i) == 1:
                ans += i
        return ans

We can use O(N) space and O(N) time to count the elements in the numbers.

1
2
3
4
5
6
7
8

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        ans = 0
        c = Counter(nums)
        for i in nums:
            if c[i] == 1:
                ans += i
        return ans

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        ans = 0
        c = Counter(nums)
        for i in nums:
            if c[i] == 1:
                ans += i
        return ans

The overall time complexity is improved to O(N) at the cost of using a hash table Counter() object.

1
2
3
4

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        c = Counter(nums)
        return sum(i for i in nums if c[i] == 1)

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        c = Counter(nums)
        return sum(i for i in nums if c[i] == 1)

See also: Teaching Kids Programming – Sum of Unique Elements

–EOF (The Ultimate Computing & Technology Blog) —